整除

b=a*q,b可被a整除
1. 除 a除b  == b/a  ==  b除以a
2. a整除b   == b%a=0

同余

1. a同余2(mod n)  a%n==2
2. (a+b)%n => (a%n+b%n)%n
3. (a*b)%n => (a%n)*(b%n)%n

最小公倍数lcm 和最大公约数gcd

1.lcm(a,b)=(a*b)/(gcd(a,b);
2.if(n%m)==r 求gcd(n,m)?  ==>gcd(m,r);
3.先除再乘可以防止爆int
4.系统自带__gcd(a,b);

质数

除一和它本身能够整除
质数筛法：
1.先假设每个数是质数，bool p[N]=true;==>memset(p,0xff,sizeof p);
2.从2开始枚举每个数的倍数，变成非质数p[i]=false;
积性函数：
1. f(mn)=f(n)*f(m)  , 所有gcd(m,n)==1
2. 满足以上性质的一类函数
欧拉函数：
1.  小于等于n的所有数中与n互质的数的个数，欧拉函数是积性函数  n是正整数
        ==> g(i,n)=1 1<=i<=n  有多少个i?
2.  f(12)=4  => 1 5 7 11  都与12互质
3.  f(12)=12*(1-(1/2))*(1-(1/3))
4.  f(n)=n*(1-(1/p1))*(1-(1/p2))...  p数组为n的质因数

算术基本定理

N = P1^a1 * P2^a2 * … * Pn^an
则N的约数个数为(a1+1)(a2+1)…(an+1)

假设N的一个约数为D

D = P1^b1 * P2^b2 * … * Pn^bn
其中bi可以取到0，范围是0<= bi <= ai

因为只有和N的质因数一一对应一定能得到约数
因为bi可以从0取到ai,那么每一个bi就有(ai+1)种选法

约数的个数就是每个bi对应多少种选法相乘
即约数个数就为(a1+1)(a2+1)…(an+1)

约数之和S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

扩展欧几里得

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

但是我们得扩展欧几里得定理只能求 -an+bd = gcd(n,d)中的a和b，但是很容易看出y-x应该为gcd(n,d)的整数倍
否则无解。
因此我们只需要判断y-x是否为gcd(n,d)的整数倍就能判断是否有解了。
若有解我们利用扩展欧几里得定理就可以求得-an+bd = gcd(n,d)中的a和b，然后将a和b扩大 (y-x)/gcd(n,d)倍
就可以得到一组a0和b0，因为之前我们证过了获得一组解后其他解就可以表示出来了，我们只需要求一下所有解中的最小值就可以了（注意我们的b只能是正数，你总不能让大圣反着翻吧）
即：
求一下b = b0+k*(n/gcd(n,d))的最小值即可
minb = b0%(n/gcd(n,d));

矩阵

矩阵乘法

 struct matrix{
     int n,m;
     int a[N][N];
 }
 matrix matrix_mul(matrix A , matrix B)
 {
     matrix C;
     C.n=A.n;
     C.m=B.m;
     for(int i=0;i<A.n;++i)
     {
         for(int j=0;j<B.m;++j)
         {
             C.a[i][j]=0;
             for(int k=0;k<A.m;++k)
             {
                 C.a[i][j]+=A.a[i][k]*B.a[k][j];
             }
         }
     }
     return C;
 }

矩阵二分幂/快速幂

 matrix matrix_pow(matrix A ,int n ,int mod)//一般矩阵为n*n
 {
     matrix res=unit(),temp=A;
     for(;n;n/=2)
     {
         if(n&1){
             res=matrix_mul(res,temp,mod);
         }
         res=matrix_mul(temp,temp,mod);
     }
 }

更相减损术–一般用于指数幂的最大公约数

LL gcd_sub(LL a,LL b)  
{
    if(a<b)  swap(a,b);  //更相减损术总是大减小（它们的底数是一样的）
    if(b==1)  return a;
    return gcd_sub(b,a/b);
}