Contents
    1.前置知识点
    2.扩展欧几里得算法
    3.质数与欧拉筛法
    4.容斥原理
    5.欧拉函数
    6.高斯消元
    7.矩阵乘法
    8.卡特兰数 
    9递归法求组合数
    10.Lucas定理
    11.NIM游戏
    12.公平组合游戏ICG
    13.斯特林数
    14.积性函数的运用
    15.莫比乌斯函数与莫比乌斯反演
    --------------------------------------------------------------------------------------------------------------------
1.前置知识点
--------常用的数学符号---------
   ⌊x⌋表示x向下取整
   ⌈x⌉表示x向上取整
   [exp]其中exp代表一个表达式，如果表达式为真，值为1，表达式值为假，结果为0
    gcd(x,y)表示x与y的最大公约数
   lcm(x,y)表示x与y的最小公倍数、
   d|n表示d整除n，n是d的倍数
   a≡b(mod n)表示a,b在模的意义下同余a

 1.1快速幂
 1.a^b  mod k(a,b均不超过10^6)
ab%k=(a%k)*(b%k)%k
将b进行二进制分解
(1)b= b0*2^p0 + b1*2^p1 + b2*2^p2 ... + bn*2^pn , 其中p0~pn是二进制位数，b0~bn是二进制对应位置是0还是1.
(2)a^b = a^(b0*2^p0) * a^(b1*2^p1) ... * a^(bn*2^pn)
(3)如果 bi=0, 则 a^(bi*2^pi) = 1, 则不用计算
因此关键是循环遍历b并判断b的二进制位数上的数字是1还是0
 代码表示: 
Int ans=1;
While(b)
{
     if(b &1) ans=ans*a mod p;
//a^b中b分解为二进制数，当每次从右往左向前遍历b的二进制数位时；前一位是后一位的2倍；而a^b就更新为a=a^2  mod p
        b>>=1;
        a=a*a mod p;  
}
Return ans;

1.2.a*b mod k(a,b均不超过10^6)
把 b写成二进制形式，然后如果某位上为1就加上它a*（2^n）次方（n与这位的位置有关）
并且每次计算后取模就可以了
例：计算 3*7

7的二进制 111
3*(1*2^0)=3
3*(1*2^1)=6
3*(1*2^2)=12

观察可发现每次的可由前一次*2推出(记得取模)
时间复杂度分析：logn
代码表示: 
 ll  res=0;
   while(b)
   {
       if(b&1) res=(res+a)%p;//因为取模的优先级高于加减法
       b>>=1;
       a=a*2%p;
   }
   cout<<res<<endl;
2.欧几里得算法
（1)求 gcd(x,y) 
  (2)d|x , d|y等价于d|(x-y),d|x
  (3)gcd(x,y)=gcd(x-y,y)=gcd(y,x%y)
  (4)显然每次取模后数字的大小至少折半，所以复杂度是低于O（log max(x,y)）
代码表示：
Int gcd(int x,int y)
{
   if(!y)return x;
  return gcd(y,x%y);

}

3.取整问题
∑26_(k=1)^n▒⌊n/k⌋   n≤1e9
假设n=5;
 5/1 5/2 5/3 5/4 5/5
   5     2   1     1     1
不防设 x=n/l ----表示x向下取整(l为连续相同数字区间的左端点)
           n>=x*r->r=n/x->r=n/(n/l)
代码表示：
     Long long ans=0;
        Cin>>n;
    For(int l=1,r=1;l<=n;l=r+1)
    {
       r=n/(n/l);
     ans+=n/l*(r-l+1);
    }
    Cout<<ans<<endl;

1.3.取整与取模的转换
 n mod m=n-m⌊n/m⌋
求∑26_(k=1)^n▒〖n mod k〗
∑26_(k=1)^n▒〖n mod k〗=n∗n−∑26_(k=1)^n▒k⌊n/k⌋ 

代码表示：
   Long long ans=0;
        Cin>>n;
    For(int l=1,r=1;l<=n;l=r+1)
    {
       r=n/(n/l);
     ans+=(r-l+1)*(l+r)/2*n/l*(r-l+1);//l,l+1,……,r的区间和
    }
    Cout<<ans<<endl;

2逆元
(1)同余方程 ax≡b(mod m)则等价于求 
ax=m∗(−y)+b;ax+my=b
有解条件为 gcd(a,m)|b,然后用扩展欧几里得求解即可
特别的 当 b=1且 a与m互质时 则所求的x即为a的逆元,则记为x是a的逆元，a^-1

2.1扩展欧几里得

证明：当 b=0 时 ax+by=a 故而 x=1,y=0
当 b≠0 时,因为gcd(a,b)=gcd(b,a%b)
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
故而,x=y′,y=x′−⌊a/b⌋∗y′

（2）对于特殊方程 ax+by=1；
 a(x+b*a/a)+b(y-a*b/b )=1
 a(x+b)+b(y-a)=1
 (x+k*b,y-k*a)综合表示为(x%b+b)%b;

代码表示：
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
2.2.线性同余方程
给定n组数据ai,bi,mi，对于每组数求出一个xi，使其满足ai∗xi≡bi(mod mi)
则其等价于 ax=my+b，即ax+my=b求解其x,y,<->k*gcd(a,m)|b
因此先用扩展欧几里得算法求出一组整数 x0,y0, 使得 a∗x0+m∗y0=gcd(a,m)。
过程：


ai∗xi≡bi(mod mi)
根据裴蜀定理知，d=gcd(a,m)<->gcd(a%m,a)|b<->b%d=0时，该线性同余方程有整数解
 ai*x=k*gcd(a,m)(mod mi)
因此x1=kx0(k=b/gcd(a,m))
代码表示：
int exgcd(int a,int b,int &x,int &y)
{
     if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 

}
int main()
{
    int n,x,y;
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if(b%d)puts("impossible");
        else cout<<x*(b/d)%m<<endl;//(x*(b/d)%m)%m
    }

3.整数的唯一分解定理
算术基本定理：任何一个大于1的自然数N,如果N不为质数算术基本定理：任何一个大于1的自然数N,如果N不为质数 ,那么N可以唯一分解成有限个质数的乘积N=p1a1∗p2a2…∗pnan那么N可以唯一分解成有限个质数的乘积N=p1a1∗p2a2…∗pnan,且最多只有一个大于n√的质因子，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。

(2)试除法判定质数模板（O（√n)  )
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
(3)筛选出1-n中的质数个数
1.朴素筛法模板O(nlogn)
时间复杂度：n/2+n/3+…+n/n=n(1/2+1/3+…+1/n)=n ∗⁡〖〖log〗_e n〗<nlogn
void get_primes2(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;//表示没有被筛过，因此把此素数存起来
        for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
}
2.诶氏筛法模板 -素数筛法O(nloglogn)
质数定理：1-n中有n/lnn 个质数
void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}
3..线性筛法模板-欧拉筛法 O(n)
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    { 
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )//假设n是合数,那么在√n 之前一定会被它的最小质因子筛完
        {
            st[primes[j] * i] = true;//primes[j]是i的最小质因子，也是primes[j]*i的最小质因子
            if (i % primes[j] == 0) break;
        }
    }
}
4.容斥原理


5.欧拉函数
1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)。
若在算数基本定理中,N=p1a1p2a2…pmam，则：
ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pm

证明：
从1到  ps_^as   中共有 ps_^as  个数字
其中与 ps_^as  不互质的有ps,2ps,…,p_^█(as−1@s)∗ps ,共p_^█(as−1@s) 项
所以 φ(p_^█(as@s)) =  p_^█(as@s)- p_^█(as−1@s)=p_^█(as@s)∗(1−1/p_s )
因此
φ(n)=φ(pa11)∗…∗φ(paxx)
=(p1a1−p1a1−1)∗…∗(pxax−pxax−1)
=pa11∗(1−1p1)∗pa22∗(1−1p2)∗…∗paxx∗(1−1px)
=p1a1∗p2a2∗…∗pxax∗(1−1p1)∗(1−1p2)∗…∗(1−1px)
=N∗∏i=1x(1−1pi)

C++代码：
int x,res;
        cin>>x;
        res=x;
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0)
            {
                while(x%i==0)
                    x/=i;
                res=res/i*(i-1);
            }
        }
        if(x>1) res=res/x*(x-1);
        cout<<res<<endl;

(2)线性筛法求欧拉函数
1.当I % pj=0时,说明i是pj的倍数，也说明了pj是i的一个因子，求i的质因子同时也就包含了求pj的质因子，
因此求pj*i的质因子也就是在求i的质因子个数的基础上多乘以pj这个数。
Phi(i)=i*(1-1/p1)……（1-1/pk)
Phi(pj*i)=pj*phi(i)；
2.当i%pj!=0时,i%pj,说明pj和i互质而且pj也是i*pj的一个质因子，
因此pj*i的质因子比i的质因子多pj这个质因子。
Phi(i)=i*(1-1/p1)……*（1-1/pk);
Phi(pj*i)=pj*i*(1-1/p1)……*（1-1/pk)*(1-1/pj);
Phi(pj*i)=phi(i)(pj-1);

C++代码：
void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1; 
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j]; 
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}
6.高斯消元解线性方程组
下图为一个包含m个方程n个未知数的线性方程组示例：


如果给定线性方程组存在唯一解，则输出共n行，其中第i行输出第i个未知数的解，结果保留两位小数。
如果给定线性方程组存在无数解，则输出“Infinite group solutions”。
如果给定线性方程组无解，则输出“No solution”。
C++代码：
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=1e-6;
double a[N][N];
int n;
int gauss()
{
    int c,r;//c列r行
    for( c=0,r=0;c<n;c++)
    {
             int t=r;
        for(int i=r;i<n;i++)
             if(fabs(a[i][c]) > fabs(a[t][c]))
               t=i;//该列最大值所在的行号

            if(fabs(a[t][c])< eps) continue;//当前列当前行的最大值为0，就不用进行交换化解
          for(int i=c;i<=n;i++)swap(a[t][i],a[r][i]);//从第c列依次往后将第t行上的所有数交换到第一行上
            for(int i=n;i>=c;i--) a[r][i]/=a[r][c];//把首行最大值的系数化为1
             //依次从r+1行开始，从右往左依次将r+1行上的每一个数-=a[r][j]*a[i][c]，将第r+1行的第一个数化为0
               for(int i=r+1;i<n;i++)
               if(fabs(a[i][c])>eps)//改行首元素非零
               for(int j=n;j>=c;j--)
               a[i][j]-=a[r][j]*a[i][c];//将当前行的第一个数变为0;
                     r++;//将当前一行下移一行继续化简操作
    }
       if(r<n) //r表示行数少于未知数的个数
       {
           for(int i=r;i<n;i++)
              if(fabs(a[i][n])>eps)//第i列n行的系数不为0，但其结果为0，俗称0=!0
                return 2;//无解
                return 1;//无穷多组解
       }  

       //倒着带回求解上三角矩阵方程对应x的值
        for(int i=n-1;i>=0;i--)
             for(int j=i+1;j<n;j++)
                 a[i][n]-=a[i][j]*a[j][n];
    return 0;//有唯一解
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
       for(int j=0;j<n+1;j++)
          cin>>a[i][j];
          int t=gauss();
          if(t==0)
          {
              for(int i=0;i<n;i++)
                  printf("%.2lf\n",a[i][n]);
          }
         else if(t==1)cout<<"Infinite group solutions"<<endl;
          else cout<<"No solution"<<endl;
        return 0;
}
7.矩阵乘法

C++代码：
//二阶矩阵相乘
void Matrix_Multiply(int A[][N], int B[][N], int C[][N]) { 
     for(int i = 0; i < 2; i++) {  
        for(int j = 0; j < 2; j++) {  
           C[i][j] = 0;        
           for(int t = 0; t < 2; t++) {  
              C[i][j] = C[i][j] + A[i][t] * B[t][j];          
           }    
        }          
     }  
}  

8.卡特兰数 

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)

C++代码：
int qmi(int a, int k ,int p)
{
    int res=1;
    while(k)
      {
          if(k & 1 ) res=(ll) res* a % p;
             k>>=1;
             a=(ll)a*a %p;
      }
      return res;
}
int main()
{
    int n;
    cin>>n;
    int a=2*n,b=n;
    int res=1;
    for(int i=a;i>a-b;i--) res=(ll)res * i % mod;
      for(int i=1;i<=b;i++)res=(ll)res*qmi(i,mod-2,mod) % mod;
        res=(ll)res*qmi(n+1,mod-2,mod) % mod;
        cout<<res<<endl;
        return 0;

}

9递归法求组合数
C++代码：
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

（2通过预处理逆元的方式求组合数
C++代码：
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
10.Lucas定理
给定nn组询问，每组询问给定三个整数a,b,pa,b,p，其中pp是质数，请你输出Cba mod pCab mod p的值。

C++代码：
若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
Int qmi(int a, int k)       // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b)     // 通过定理求组合数C(a, b)
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}
int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

11.NIM游戏
给定nn堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。
C++代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int res=0;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        res^=x;
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}
12.公平组合游戏ICG
若一个游戏满足：
1.由两名玩家交替行动；
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3.不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

13.斯特林数

s(n,m)=(n-1)*s(n-1,m)+s(n-1,m-1)
S(n,m)=m*S(n-1,m)+S(n-1,m-1)

14.积性函数的运用
积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。
完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数。

15.莫比乌斯函数与莫比乌斯反演
1.莫比乌斯函数

（1）证明：
考虑n的唯一分解与莫比乌斯函数的容斥过程
C(m,奇数)-C(m,偶数)=[m=1]
莫比乌斯函数就是为了满足容斥的形式所构造的
（2）性质的运用：