1.筛法

void get_prime1()
{
    for(int i=2;i<=n;++i){
        if(!st[i])
            primes[cnt++]=i;
        for(int j=i;j<=n;j+=i)
            st[j]=true;
    }
}//朴素筛法，通过当前i筛去i的倍数O(nlogn)
void get_prime2()
{
    for(int i=2;i<=n;++i){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i)
            st[j]=true;
        }
    }
}//诶式筛法，任何一个合数都是素数的倍数时间复杂度O(nloglogn)
void get_prime3()
{
    for(int i=2;i<=n;++i){
        if(!st[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)//优化，不筛大于n的合数
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)//i是当前质因子的倍数
            break;
        }
    }
}//线性筛法O(n)

2.约数

     //1.约数个数

     (p1+1)(p2+1).....(pn+1)

     //2.约数之和

     (p1^0+p1^1+.....p1^n)(p2^0+p2^1.....)(pn^0+pn^1+pn^2........)

     //3.最大公约数

     int gcd(int a,int b){
         return b?gcd(b,a%b):a;
     }//欧几里德辗转相除法

3.欧拉函数

//1.欧拉函数定义

/*
         欧拉函数定义：对于整数n来说，1～n与n互质的数的个数
         fx(N)=N*(p1-1)/p1 *(p2-1)/p2*........(pn-1)/pn;
         p1到pn为整数N指数表现形式下的底数

*/

//2.筛法求欧拉函数
//筛法求欧拉函数是基于线性筛的基础上，结合欧拉函数公式推导出来的，如果不明白可以把公式写一下推倒一下
void get_primes(int n)
{
    euler[1]=1;
    for(int i=2;i<=n;++i){
        if(!st[i]){
            primes[cnt++]=i;
            st[i]=true;
            euler[i]=i-1;//i为质数是前n-1个数均互质
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0){
                euler[t]=euler[i]*primes[j];//primes[j]为i的最小质因子时只需要对N*primes[j]
                break;
            }
            euler[t]=euler[i]*(primes[j]-1);//primes[j]为t的最小质因子时相当于又增加一个因子
        }
    }
}

4.快速幂

# include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
         逆元：前提：b能整除a，且a，b为整数，b和m互质
         求b模m的逆元即 a/b同余于a*x(mod m),求a
         a同余于a*b*x(mod m)，即b*x同余于1(mod m)
         费马小定理，当m为质数时
         b^(m-1)同余于1(mod m)
         等价于b*b^(n-2)同余于1(mod m)
         b^(n-2)即为逆元
*/
int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}//快速幂板子，快速幂基本原理通过增长底数来降低指数来降低时间复杂度，求mod余数
int main()
{
    int n;cin>>n;
    while(n--)
    {
        int a,p;
        cin>>a>>p;
        if(a%p==0)
        cout<<"impossible"<<endl;
        else
        cout<<qmi(a,p-2,p)<<endl;
    }
    return 0;
}

5.扩展欧几里得

//1.a*x+b*y=gcd(a,b);
/*
      d=gcd(a,b); a*x+b*y=d;
      gcd(a,b)=gcd(b,a%b)= b*x1+a%b*y1 = b*x1+y1*(a-a/b*b) = a*y1+b*(x1-a/b*y1);

      x=y1,y=x1-a/b*y1;

*/
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;
}
//2.线性同余方程
/*
      通解=特解+齐次解
      a*x+b*y=d;

      特解：gcd(a,b)|d,即先通过1求得一般解，
      a*(x*d/gcd(a,b))+b*(y*d/gcd(a,b)) = d;

      齐次解：a*x+b*y = 0; d=gcd(a,b);
      x = k*b/d, y = -k*a/d  (k为整数)
      即最终解为：
      x = x + k*b/d;y = y - k*a/d;
*/

//3.求解逆元
/*
    b*x同余于d(mod m),可转化为 b*x = -my + d; b*x + m*y = d;
    用扩展欧几里得即可求解得 x,y;
    当 d = 1,且b与m互质时，x即为所求的逆元
*/

6.组合数

/*
    组合数1.0:  公式：C[n][m] = C[n-1][m] + C[n-1][m-1];
                证明：从n个数挑选m个数等价于从n-1个数挑选m个的方案数加上从n-1个数挑选m-1个的方案数
                时间复杂度：需要两重循环复杂度为O(nm)

    组合数2.0： 求C[n][m]，通过求逆元求解
                1.最后mod的余数为质数直接使用快速幂来求 
                2.不为质数则可以通过扩展欧几里得算法来求得最终解。
                时间复杂度：仅需要一重循环分别用数组来存n和m的阶乘和逆元 O(n)

    组合数3.0： 当n和m足够大时，可以应用卢卡斯定理：C[a][b] = C[a/p][b/p] * C[a%p][b%p] (mod p)
                对于C[a/p][b/p],可以通过递归直到a<p&&b<p来求得
                再结合2.0即可
                时间复杂度：我不知道

    卡特兰数：  数列计数问题，可以通过坐标来实现具体算法
*/ 

7.容斥原理

 //

8.博弈论

 /*
       1.Nim游戏：
       结论：对于每一个Nim游戏 a1^a2^.....an!=0 先手必胜
       通常情况下需要对题目进行稍微变形再通过Nim游戏结论来完成

       2.SG函数
       Mex函数：当前节点的Mex值是不包含与当前节点相连的边Mex值的最小自然数，没有出边的顶点sg值为0
       多个独立局面的SG值，等于这些局面SG值的异或和。
       3.
       有向图游戏的和
       设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,
       并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
       有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
       SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)
*/