快速幂

int power(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;

}

费马小定理求逆元

概念:费马小定理:若p是质数且a,p互质 则 a^(p-1)≡1(mod p)

同余式 :若a%p==b%p 则a≡b(mod p) 即 a mod p=b
逆元   :若a,p互质且 ax≡1(mod p) x为a在mod p下的逆元
a在mod p下的逆元为 power(a,p-2,p)

裴蜀定理

一定存在整数x,y,使得 ax+by=gcd(a,b)

扩展欧几里得

//求方程ax+by=gcd(a,b) 的一个特解
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

扩展欧几里得求同余方程

求同余方程 a≡b(mod m)
a≡b(mod m) => ax+my=b

    int a,b,m,x,y;
    cin>>a>>b>>m;
    int d=exgcd(a,m,x,y);
    //当b为gcd(a,m)的整数倍时,有整数解 
    if(b%d==0){
        cout<<x*b/d%m<<endl;
    } else{
        cout<<"无整数解"<<endl;
    }

扩展欧几里得求逆元

求同余方程 ax≡1(mod m) (a,m互质)
ax≡1(mod m) => ax+my=gcd(a,m)=1

    int a,m,x,y;
    cin>>a>>m;
    int d=exgcd(a,m,x,y);

    cout<<(x%m+m)%m<<endl;

中国剩余定理

求同余方程
x≡r1(mod m1)
x≡r2(mod m2)
. . .
x≡rn(mod mn) (其中m1,m2,…,mn互质)

//sum(ri*ci*ci-1)
ll CRT(){
    ll M=1,ans=0;
    for(int i=0;i<n;i++){
        M*=m[i];
    }
    for(int i=0;i<n;i++){
        ll c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        ans=(ans+r[i]*c*x%M)%M;
    }
    return (ans%M+M)%M;

}

扩展中国剩余定理

ll exCRT(){
    ll m1,m2,r1,r2,p,q;
    m1=m[0];r1=r[0];
    for(int i=1;i<n;i++){
        m2=m[i];r2=r[i];
        ll d=exgcd(m1,m2,p,q);
        if((r2-r1)%d) return -1;
        p=p*(r2-r1)/d;
        p=(p%(m2/d)+m2/d)%(m2/d);
        r1=m1*p+r1;
        m1=m1*m2/d;
    }
    return (r1%m1+m1)%m1;
}