数论模板

int ex_gcd(int a,int b,int &x,int &y)
{
    int t,d;
    if(b==0)
    {
        x=1;
        y=0;   
        return a;
    }
    d=ex_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;  
    return d;
}
/*
    处理的只是NN'+MM'=d的N',M'的值
*/
ex_gcd
#include<stdio.h>
#include<string.h>
int ex_gcd(int a,int b,int &x,int &y)
{
    int t,d;
    if(b==0)
    {
        x=1;
        y=0;   
        return a;
    }
    d=ex_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;  
    return d;
}
/*
    处理的只是NN'+MM'=d的N',M'的值
*/

int R[20];
int M[20];
bool flag;
int main()
{
    int a,b,i;
    int M1,M1t,M2,M2t,R1,R2;
    int len,T;
    int d;
    int N;
    int cas;
    scanf("%d",&T);
    for(cas=1;cas<=T;cas++)
    {
        /*X问题 
        scanf("%d",&N);
        */
        scanf("%d",&len);
        memset(R,0,sizeof(R));
        memset(M,0,sizeof(M));
        flag = 0;
        for(i=0;i<len;i++)scanf("%d",&M[i]);
        for(i=0;i<len;i++)scanf("%d",&R[i]);
        //init
        M1 = M[0];
        R1 = R[0];
        for(i=1;i<len;i++)
        {
            M2 = M[i];
            R2 = R[i];

            d = ex_gcd(M2,M1,M2t,M1t);
            if((R2-R1)%d!=0)
            {
                flag = 1;
                break;
            }
            int t = M2/d;

            M1t = ((R2-R1)/d*M1t%t+t)%t;
            
            R1 =  M1*M1t+R1;

            M1 = M1/d*M2;
        }
        if(R1==0){R1 = M1;} //很重要。  比如 mod 1 = 0 这样的 就能排除了答案是0.
                            //另外对于 mod1 = 2的可以在输入的时候判断。非法即可。
        //Hello Kitty
        if(flag){printf("Case %d: %d
",cas,-1);}
        else {printf("Case %d: %d
",cas,R1); }


        /*X问题
        if(flag||R1>N){printf("0
");}
        else
        {
        int count = (R1-B1)/M1+1;
         printf("%d
",count);
        }
        */
    }
}
/*
X mod M1 = R1;
X mod M2 = R2;
X = R1 + M1M1';
X = R2 + M2M2';

M1M1'-M2M2' = R2-R1;

M1M1'+M2(-M2') = R2-R1;
我们并不管M2'所以完全可以的。且必须是R2-R1.这样。M1'才是M1' 不会是 -M1'

cal : 最小M1'   (((R2-R1)/d)*M1'% t + t) % t  
PS : (R2-R1)/d 不要忘记。

cal : 最小X  X = M1'M1 + R1.
令    R1 = X
    M1 = lcm(M1,M2).

关于这种式子的安排。
可以这样。
在外围附上 式1.
然后循环 式2.
把结果弄到式1上。

对于 X问题 hdu 
统计个数：
R1 是最后的最小X。M1为M集合的最小公倍数
那么R1 + k * M1 = n <= N
计算k.
注意题设：
R1 为正整数。所以R1=0时 count--。
对于 Hello KItty
*/
中国剩余定理
//针对Chinese remainder theorem again
#include<stdio.h>
#include<string.h>

__int64 ex_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
    __int64 t,d;
    if(b==0)
    {
        x=1;
        y=0;   
        return a;
    }
    d=ex_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;  
    return d;
}
/*
    处理的只是NN'+MM'=d的N',M'的值
*/

__int64 R[20];
__int64 M[20];
bool flag;
int main()
{
    __int64 a,b;
    __int64 M1,M1t,M2,M2t,R1,R2;
    int len,T;
    __int64 d;
    int N;  
    int i;
        /*X问题 
        scanf("%d",&N);
        */
    while(scanf("%I64d%I64d",&len,&a)!=EOF)
    {
        if(len==0&&a==0){break;}
        memset(R,0,sizeof(R));
        memset(M,0,sizeof(M));
        flag = 0;
        for(i=0;i<len;i++)scanf("%I64d",&M[i]);
        for(i=0;i<len;i++)R[i] = M[i]-a;
        //init
        M1 = M[0];
        R1 = R[0];
        for(i=1;i<len;i++)
        {
            M2 = M[i];
            R2 = R[i];

            d = ex_gcd(M2,M1,M2t,M1t);
            int t = M2/d;

            M1t = ((R2-R1)/d*M1t%t+t)%t;
            
            R1 =  M1*M1t+R1;

            M1 = M1/d*M2;
        }
        if(R1==0){R1 = M1;} //很重要。  比如 mod 1 = 0 这样的 就能排除了答案是0.
                            //另外对于 mod1 = 2的可以在输入的时候判断。非法即可。
        //Hello Kitty
 
       printf("%I64d
",R1);


        /*X问题
        if(flag||R1>N){printf("0
");}
        else
        {
        int count = (R1-B1)/M1+1;
         printf("%d
",count);
        }
        */
    }
}
/*
X mod M1 = R1;
X mod M2 = R2;
X = R1 + M1M1';
X = R2 + M2M2';

M1M1'-M2M2' = R2-R1;

M1M1'+M2(-M2') = R2-R1;
我们并不管M2'所以完全可以的。且必须是R2-R1.这样。M1'才是M1' 不会是 -M1'

cal : 最小M1'   (((R2-R1)/d)*M1'% t + t) % t  
PS : (R2-R1)/d 不要忘记。

cal : 最小X  X = M1'M1 + R1.
令    R1 = X
    M1 = lcm(M1,M2).

关于这种式子的安排。
可以这样。
在外围附上 式1.
然后循环 式2.
把结果弄到式1上。

对于 X问题 hdu 
统计个数：
R1 是最后的最小X。M1为M集合的最小公倍数
那么R1 + k * M1 = n <= N
计算k.
注意题设：
R1 为正整数。所以R1=0时 count--。
对于 Hello KItty
*/
中国剩余定理高精度
    #include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<algorithm>  
    #include<cmath>  
    #define LL __int64  
    #define N 1000000  
    using namespace std;  
    struct Node{  
        int idx;  
        LL val;  
    }baby[N];  
    bool cmp(Node n1,Node n2){  
        return n1.val!=n2.val?n1.val<n2.val:n1.idx<n2.idx;  
    }  
    LL PowMod(LL a,LL b,LL MOD){  
        LL ret=1;  
        a%=MOD;  
        while(b){  
            if(b&1)  
                ret=((LL)ret*a)%MOD;  
            a=((LL)a*a)%MOD;  
            b>>=1;  
        }  
        return ret;  
    }  
    //二分查找  
    int BinSearch(int m,LL num){  
        int low=0,high=m-1,mid;  
        while(low<=high){  
            mid=(low+high)>>1;  
            if(baby[mid].val==num)  
                return baby[mid].idx;  
            if(baby[mid].val<num)  
                low=mid+1;  
            else  
                high=mid-1;  
        }  
        return -1;  
    }  
    int main(){  
        LL p,b,n;  
        while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF){  
            int m = (int)ceil(sqrt((double)(p - 1)));  
            baby[0].idx=0;baby[0].val=1;  
            for(int i=1;i<m;i++){  
                baby[i].idx=i;       
                baby[i].val=((LL)baby[i-1].val*b)%p;   //b^i  
            }  
            sort(baby,baby+m,cmp);  
            int cnt=1;  
            //去年余数相同但是标号大的  
            for(int i=1;i<m;i++)  
                if(baby[i].val!=baby[cnt-1].val)  
                    baby[cnt++]=baby[i];  
            LL bm=PowMod(PowMod(b,p-2,p),m,p);//先求逆元，再求b^(-m)  
            int ans=-1;  
            LL tmp=n;  
            for(int j=0;j<m;j++){  
                //查找(b^(-m))^j  
                int pos=BinSearch(cnt,tmp);  
                if(pos!=-1){  
                    ans=j*m+pos;  
                    break;  
                }  
                tmp=((LL)tmp*bm)%p;  
            }  
            if(ans<0)  
                puts("no solution");  
            else  
                printf("%d
",ans);  
        }  
        return 0;  
    }
Baby step Giant step
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<cmath>  
#define LL __int64  
#define N 1000000  
using namespace std;  
struct Node{  
    int idx;  
    int val;  
}baby[N];  
bool cmp(Node n1,Node n2){  
    return n1.val!=n2.val?n1.val<n2.val:n1.idx<n2.idx;  
}  
int gcd(int a,int b){  
    return b==0?a:gcd(b,a%b);  
}  
int extend_gcd(int a,int b,int &x,int &y){  
    if(b==0){  
        x=1;  
        y=0;  
        return a;  
    }  
    int gcd=extend_gcd(b,a%b,x,y);  
    int t=x;  
    x=y;  
    y=t-a/b*y;  
    return gcd;  
}  
int inval(int a,int b,int n){  
    int e,x,y;  
    extend_gcd(a,n,x,y);  
    e=((LL)x*b)%n;  
    return e<0?e+n:e;  
}  
int PowMod(int a,int b,int MOD){  
    LL ret=1%MOD,t=a%MOD;  
    while(b){  
        if(b&1)  
            ret=((LL)ret*t)%MOD;  
        t=((LL)t*t)%MOD;  
        b>>=1;  
    }  
    return (int)ret;  
}  
int BinSearch(int num,int m){  
    int low=0,high=m-1,mid;  
    while(low<=high){  
        mid=(low+high)>>1;  
        if(baby[mid].val==num)  
            return baby[mid].idx;  
        if(baby[mid].val<num)  
            low=mid+1;  
        else  
            high=mid-1;  
    }  
    return -1;  
}  
int BabyStep(int A,int B,int C){  
    LL tmp,D=1%C;  
    int temp;  
    for(int i=0,tmp=1%C;i<100;i++,tmp=((LL)tmp*A)%C)  
        if(tmp==B)  
            return i;  
    int d=0;  
    while((temp=gcd(A,C))!=1){  
        if(B%temp) return -1;  
        d++;  
        C/=temp;  
        B/=temp;  
        D=((A/temp)*D)%C;  
    }  
    int m=(int)ceil(sqrt((double)C));  
    for(int i=0,tmp=1%C;i<=m;i++,tmp=((LL)tmp*A)%C){  
        baby[i].idx=i;  
        baby[i].val=tmp;  
    }  
    sort(baby,baby+m+1,cmp);  
    int cnt=1;  
    for(int i=1;i<=m;i++)  
        if(baby[i].val!=baby[cnt-1].val)  
            baby[cnt++]=baby[i];  
    int am=PowMod(A,m,C);  
    for(int i=0;i<=m;i++,D=((LL)(D*am))%C){  
        int tmp=inval(D,B,C);  
        if(tmp>=0){  
            int pos=BinSearch(tmp,cnt);  
            if(pos!=-1)  
                return i*m+pos+d;  
        }  
    }  
    return -1;  
}  
int main(){  
    int A,B,C;  
    while(scanf("%d%d%d",&A,&C,&B)!=EOF){  
        if(B>=C){  
            puts("Orz,I can’t find D!");  
            continue;  
        }  
        int ans=BabyStep(A,B,C);  
        if(ans==-1)  
            puts("Orz,I can’t find D!");  
        else  
            printf("%d
",ans);  
    }  
    return 0;  
}
ex Baby step Giant step
int q_pow(int a, int b, int c)
{
    int ans = 1;
    int k = a % c;
    while(b>0)
    {
        if(b % 2 == 1)
            ans = (ans * k) % c;
        b = b/2;
        k = (k * k) % c;
    }
    return ans;
}
q_pow
LL phi(LL n)  
{  
    LL rea=n,i;  
    for(i=2;i*i<=n;i++)  
    {  
        if(n%i==0)  
        {  
            rea=rea-rea/i;  
            while(n%i==0) n/=i;  
        }  
    }  
    if(n>1)  
        rea=rea-rea/n;  
    return rea;  
}  
/*
 from acdreamer http://blog.csdn.net/acdreamers/article/details/8990803
*/
euler
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>

#define MAXN 10000
using namespace std;

bool isprime[MAXN+5];
int prime[MAXN+5];
int num;
int mobi[MAXN+5];
int euler[MAXN+5];
int Min(int a,int b){return a>b?a:b;}

void Sieve()
{
    int i,j;
    num = 0;

    mobi[1] = 1; // multiply function
    memset(mobi,0,sizeof(mobi));

    euler[1] = 1;
    memset(euler,0,sizeof(euler));

    memset(prime,0,sizeof(prime));
    memset(isprime,0,sizeof(isprime));

    for(i=2;i<=MAXN;i++)
    {
        if(!isprime[i])
        {
            prime[num++] = i;
            mobi[i] = -1;
            euler[i] = i-1;
        }
        for(j=0;j<num;j++)
        {
            if(i*prime[j]>MAXN){break;}
            isprime[i*prime[j]] = 1;
            if(i%prime[j]==0)
            {
                mobi[i*prime[j]] = 0;
                euler[i*prime[j]] = euler[i]*prime[j];
                break;
            }
            else
            {
                mobi[i*prime[j]] = mobi[prime[j]]*mobi[i];
                euler[i*prime[j]] = euler[prime[j]]*euler[i];
            }
        }
    }
}

int main()
{
    int i;
    Sieve();
    /*isprime[i] 0为素数 1为合数*/
    for(i=1;i<100;i++)
    {
        printf("%d %d %d %d
",isprime[i],prime[i],euler[i],mobi[i]);
    }
}
Sieve
LL q_pow(LL a, LL b, LL c)
{
    LL ans = 1;
    LL k = a % c;
    while(b)
    {
        if(b & 1)
            ans = (ans * k) % c;
        b >>= 1;
        k = (k * k) % c;
    }
    return ans;
}
LL q_pow
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>

#define MAXN 10000
using namespace std;

bool isprime[MAXN+5];
int prime[MAXN+5];
int num;
int mobi[MAXN+5];
int euler[MAXN+5];
int Min(int a,int b){return a>b?a:b;}

void Sieve()
{
    int i,j;
    num = 0;

    
    memset(mobi,0,sizeof(mobi));
    mobi[1] = 1; // multiply function
    
    memset(euler,0,sizeof(euler));
    euler[1] = 1;
    memset(prime,0,sizeof(prime));
    memset(isprime,0,sizeof(isprime));

    for(i=2;i<=MAXN;i++)
    {
        if(!isprime[i])
        {
            prime[num++] = i;
            mobi[i] = -1;
            euler[i] = i-1;
        }
        for(j=0;j<num;j++)
        {
            if(i*prime[j]>MAXN){break;}
            isprime[i*prime[j]] = 1;
            if(i%prime[j]==0)
            {
                mobi[i*prime[j]] = 0;
                euler[i*prime[j]] = euler[i]*prime[j];
                break;
            }
            else
            {
                mobi[i*prime[j]] = mobi[prime[j]]*mobi[i];
                euler[i*prime[j]] = euler[prime[j]]*euler[i];
            }
        }
    }
}

int main()
{
    int i;
    Sieve();
    
}

　　

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Milkor/p/4509445.html