小知识点

数论部分

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e5+5;
int f[maxn];
void init()
{
    f[0]=1;
    for(int i=1;i<maxn;i++)
    {
        f[i]=0;
        int flag;
        for(int j=1;;j++)
        {
            int temp1=i-j*(3*j-1)/2;
            int temp2=i-j*(3*j+1)/2;
            if(j%2==1)
                flag=1;
            else
                flag=-1;
            if(temp1<0&&temp2<0)
                break;
            if(temp1>=0)
            {
                f[i]+=flag*f[temp1];
                f[i]%=mod;
            }
            if(temp2>=0)
            {
                f[i]+=flag*f[temp2];
                f[i]%=mod;
            }
        }
        if(f[i]<0)
            f[i]+=mod;
    }
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",f[n]);
    }
    return 0;
}
/*
题意：
问有多少种不同的方式用数字拼成n
5=1+1+1+1+1=1+1+1+2=1+2+2=1+1+3=2+3=1+4=5(共七种)
五边形数定理
公式：f[n]=∑(-1)^(k-1)*(f[n-k*(3*k-1)/2]+f[n-k*(3*k+1)/2]) 
      其中n-k*(3*k-1)/2>=0,n-k*(3*k+1)/2>=0
      分开判断 
*/

随机函数的使用

mt19937 gen(time(NULL));//随机的时间函数要写在外面才有用
void init()
{
    uniform_int_distribution<int> dis(1, n);//这个位置的两个int表示数据类型，如果要随机实数就改成real
    int flag=1;
    while(flag)
    {
        pos1=dis(gen);
        pos2=dis(gen);
        pos3=dis(gen);
        if(pos1!=pos2&&pos1!=pos3&&pos2!=pos3)
            flag=0;
        if(!check())
            flag=1;
        //printf("随机   %d %d %d\n",pos1,pos2,pos3);
    }
}

欧拉函数分解素因子
void phi(ll n)  
{  
    num=0;  
    for(int i=2;i*i<=n;i++)  
    {  
        if(n&&n%i==0)  
        {  
            while(n%i==0)  
            {  
                n/=i;  
            }  
            pri[num++]=i;  
        }  
    }  
    if(n>1)  pri[num++]=n;  
}  
 ///////
欧拉函数求个数(数组开不下可以用)
int Phi(int n)  
{  
    int i,p,ans=1;  
    for(i=2;i*i<=n;i++)  
        if(n&&n%i==0)  
        {  
            p=1;  
            while(n&&n%i==0)  
            {  
                p*=i;  
                n/=i;  
            }  
            ans*=p/i*(i-1);  
        }     
    if(n>1)  
        ans*=(n-1);  
    return ans;  
}  
//欧拉函数求区间内质因子个数
void init()  
{  
    memset(num,0,sizeof(num));  
    memset(isprime,true,sizeof(isprime));  
    isprime[1]=false;  
    for(int i=2; i<=N; i++)  
    {  
        if(isprime[i])  
        {  
            for(int j=i; j<=N; j+=i)  
            {  
                int temp=j;  
                while(temp%i==0)  
                {  
                    num[j]++;  
                    temp/=i;  
                }  
                isprime[j]=false;  
            }  
        }  
    }  
    for(int i=2; i<=N; i++)  
        num[i]=num[i]+num[i-1];  
}

//中国剩余定理
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL a[11],m[11];
//处理x%m=a对于不同的m,a解出最小的x（对于m不互质的情况也可以处理）
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL ret = exgcd(b, a%b, x, y);
    LL t = x;
    x = y;
    y = t - (a / b)*y;
    return ret;
}
LL lcm(LL a, LL b)
{
    return a / __gcd(a, b)*b;
}
LL CRT(LL m[], LL a[], int n)//n表示方程组个数
{
    LL X = a[1];
    LL LCM = m[1];
    for (int i = 2; i <= n; i++)
    {
        LL x, y;
        a[i] -= X;
        a[i] = (a[i] % m[i] + m[i]) % m[i];
        int d = exgcd(LCM, m[i], x, y);
        if (a[i] % d) return -1;
        x *= a[i] / d;
        x = (x % (m[i] / d) + m[i] / d) % (m[i] / d);
        X += LCM*x;
        LCM = lcm(LCM, m[i]);
    }
    return X;//返回值-1代表无解，其余返回最小值，可能为0
}
int main()
{
    LL p,e,i,d;
    int tt=0;
    while(~scanf("%lld%lld%lld%lld",&p,&e,&i,&d))
    {
        if(p==-1&&e==-1&&i==-1&&d==-1)
            break;
        m[1]=23,m[2]=28,m[3]=33;
        a[1]=p,a[2]=e,a[3]=i;
        LL ans=CRT(m,a,3);
        while(ans<=d) ans+=23*28*33;
        printf("Case %d: the next triple peak occurs in %lld days.\n",++tt,ans-d);
    }
    return 0;
}