是时候复习一下了

快速幂

ll pow_mod(ll a,ll b,ll p){
    ll res=1;
    while(b){
        if(b&1) res=(res*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return res;
}

素数筛

const int MAX_N=2e5+5;
bool prime[MAX_N];
void init(){
    prime[0]=prime[1]=false;
    for(int i=2;i<MAX_N;++i)   prime[i]=true;
    for(int i=2;i<MAX_N;++i){
        if(prime[i]){
            for(int j=2*i;j<MAX_N;j+=i)   prime[j]=false;
        }
    }
    return ;
}

GCD

ll gcd(ll a,ll b){
    return b==0 ? a : gcd(b,a%b);
}

推论:

1.gcd(ka,kb)=k*gcd(a,b);

2.lcm(ka,kb)=k*lcm(a,b);

3.lcm(s/a,s/b)=s/gcd(a,b);

推论3证明:

lcm(s/a,s/b)=s*lcm(b/(ab),a/(ab))= s* 1 / (ab) * lcm(a,b)=s*1/(ab)*ab/gcd(a,b)=s/gcd(a,b) 证毕

扩展GCD

void extgcd_gcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b)  d=a,x=1,y=0;
    else    extgcd_gcd(b,a%b,d,y,x) y-=x*(a/b);
}//d=gcd(a,b)

结论:

1.ax+by=1有解的条件为 gcd(a,b)=1 [反证法证明]

2.ax+by=gcd(a,b)有解,显然

3.求解ax+by=c=k*gcd(a,b)=k*d 求最小整数解x

由扩展GCD求出特解x0,y0,通解有x=x0+t*b/d,y=y0-t*a/d

令t=-x0*d/b . 则x=x0+t*b/d,if(x<0)x+=b/d 为最小整数解

欧拉定理:

如果gcd(a,n)=1,则有 a^φ(n)≡ 1 (mod n) [ n为质数，φ(n)=n-1]

孙子定理（中国剩余定理CRT)O（n）
中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组 (S)有解

//n个方程：x=a[i](mod m[i]) (0<=i<n)其中m[i]两两互质
ll china(int n, ll *a, ll *m){
ll M = 1, ret = 0;
for(int i = 1; i <= n; i ++) M *= m[i];
for(int i = 1; i <= n; i ++){
ll w = M / m[i];
ret = (ret + w * inv(w, m[i]) * a[i]) % M;
}
return (ret + M) % M;
}