数论

标签：return 数论 n% long int ans rea

 

 

 

 

 

1.贝尔数

for(int i=2;i<=n;i++){
     for(int j=0;j<i;j++){
            a[i]+=a[j]*C(i-1,j);
        }
    }

　　

2.埃氏筛

 for(int i=2;i<N/i;i++){
        if(P[i]==0)
        for(int j=i*i;j<N;j+=i)P[j]=1;
    }

　　

3.欧拉筛

for(int i=2;i<=n;i++){
        if(numlist[i]==false)prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            numlist[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        } 
    }

　　

4.唯一分解定理

long long fenjie(long long &n,long long t)
{
    if(n%t!=0)return 0;
    int sum=0;
    while(n%t==0)
    {
        n/=t;
        sum++;
    }
    return sum;
}

　　

 

5.素数环

void dfs(int depth){
    if(depth==21){
        if(isPrime(n+a[20])){
            for(int i=1;i<=20;i++)cout<<a[i]<<' ';
            cout<<'\n';
            flag=1;
        }
    }
    if(flag)return;
    for(int i=1;i<=20;i++){
        if(!p[i]&&isPrime(i+a[depth-1])){
            p[i]=1;
            a[depth]=i;
            dfs(depth+1);
            p[i]=0;
        }
    }
}

　　

6.日期问题

int days(int x,int y,int z){
    int ans=0;
    for(int i=1900;i<x;i++){
        if(leap(i))ans+=366;
        else ans+=365;
    }
    for(int i=1;i<y;i++){
        if(leap(x)&&i==2)ans+=29;
        else ans+=months[i];
    }
    return ans+z;
}

　

7.快速幂

 

long long quickPow(long long n,long long k,long long m){
    long long ans=1;
    while(k){
        if(k&1){
            ans=(ans*(n%m))%m;
        }
        n=((n%m)*(n%m))%m;
        k>>=1;
    }
    return ans;
}

　

 

8.乘法逆元

long long get_inv(long long x,long long p){
    return quickPow(x,p-2,p);
}

　　

9.整除分块

long long zcfk(long long n){
    long long res=0;
    for(long long l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        res+=n/l*(r-l+1);
    }
    return res;
}

　　

10.欧拉函数

long long Euler(long long n){
    int rea=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            rea-=rea/i;
            while(!(n%i)){
                n/=i;
            }
        }
    }
    if(n>1)rea-=rea/n;
    return rea;
}

　　

 

标签：return,数论,n%,long,int,ans,rea
From： https://www.cnblogs.com/zhanghx-blogs/p/17162166.html