试除法判定质数：

判断x是否为质数

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;
}

分解质因数：

int x;
cin >> x;
for(int i=2;i<=x/i;i ++)
{
    if(x%i==0)
    {
         int sum=0;
        while(x%i==0)
        {
            sum++;
            x=x/i;
        }
        cout << i << ' '<< sum << endl;
    }
}
if(x>1)
cout << x << ' ' << 1 << endl;//*
cout << endl;

筛质数：

int prime[N],cnt;
bool st[N];
void get_primes(int x) {
    for(int i = 2; i <= x; i++) {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= x / i; j++) {
            st[prime[j]*i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

试除法求约数：

vector<int> get_divisors(int n)
{
    vector<int> res;

    for(int i=1;i<=n/i;i ++)
    {
        if(n%i==0)
        {
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);

        }

    }
    sort(res.begin(),res.end());
    return res;
}

求一个数的约数个数：

思路：先算出一个数分解质因数后不同数字上的次方，然后每个次方都加1相乘

LL ans=1;
unordered_map<int,int> hash;
int x;
cin >> x;
for(int i=2;i<=x/i;i ++)
{
    while(x%i==0)
    {
        x=x/i;
        hash[i]++;
    }
}
if(x>1)hash[x]++;
for(auto i : hash)ans=ans*(i.second+1)%mod;//公式
cout << ans << endl;

求一个数的所有约数之和：

unordered_map<int,int> primes;
 int x;
cin >> x;
for(int i=2;i<=x/i;i ++)
{
    while(x%i==0)
    {
        x=x/i;
        primes[i]++;
    }

}
if(x>1)primes[x]++;//放在for循环外面
LL res=1;
for(auto prime:primes)
{
    int p=prime.first,a=prime.second;//**p是底数，a是指数 
    LL t=1;
    while(a--)t=(t*p+1)%mod;//求出 p0一直加到p的k的次方的和
    res=res*t%mod;
}
cout << res << endl;

求a,b的最大公约数：

int gcd(int a,int b)
{
    return b ? gcd(b,a%b):a;//b ? 意思是：b不等于0。：a的意思就是输出a。
}

求a,b的最小公倍数：

int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

欧拉函数

函数F(n)表示1~n中与n互质(公约数只有1)的个数

假设N=$P_1^{a1}$ * $P_2^{a2}$ *..... * $P_k^{ak}$

F(N)=N*(1-$\dfrac{1}{P_1}$) * (1-$\dfrac{1}{P_2}$) * .... * (1-$\dfrac{1}{P_k}$)

int x;
cin >> x;
int res=x;//res是答案**
for(int i=2;i<=x/i;i ++)
{
    if(x%i==0)
    {
        res=res/i*(i-1);    //注意先除再乘  N/pk*(pk-1);            
        while(x%i==0)x=x/i;   
    }
}
 if(x>1) res=res/x*(x-1);//注意先除再乘  N/pk*(pk-1);
cout << res << endl;

筛法求欧拉函数

求1~n中每个数的欧拉函数之和

LL 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);
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; i ++)
        res += phi[i];
    return res;
}

快速幂

求 $a^b$ mod p

int pim(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)res=(LL)res*a%p;
        b>>=1;//b右移了一位后,a也需要更新
        a=(LL)a*a%p;
    }
    return res;
}

快速幂求逆元

给定p 是质数
输入a，p求a mod p 的乘法逆元
逆元：给我们一个b让我们找到一个x使得b*x ≡ 1（mod p);
费马定理：$b^ {p-1} $ ≡ 1（mod p）可以推出 $p * b^{p-2} $ ≡ 1（mod p）。

扩展欧几里得算法

给定正整数a,b，求出一组 xi,yi，使其满足 a * xi + b * yi =gcd(a,b)。
a mod b = a - ⌊$\frac{a}{b}$ ⌋ * b

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;
}

线性同余方程

给定a,b,m，对于每组数求出一个x，使其满足a * x ≡ b (mod m)，意思是(a * x) mod m = b。
推出 a * x = m * y +b (因为是m的若干倍)，然后推出 a * x - m * y = b 。如果 b 能整除 gcd(a,m)，就有解。

高斯消元解线性方程组

输入n个方程n个未知数的线性方程组，求这个方程组。
a[i][j]表示第i行第j列的系数

int gauss()
{
    int c, r;// c 代表 列 col ， r 代表 行 row
    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 ，那么所有数都是 0，就没必要去算了，因为它的约束方程，可能在上面几行

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);//// 把当前这一行，换到最上面（不是第一行，是第 r 行）去
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// 把当前这一行的第一个数，变成 1， 方程两边同时除以 第一个数，必须要到着算，不然第一个数直接变1，系数就被篡改，后面的数字没法算
        for (int i = r + 1; i < n; i ++ )// 把当前列下面的所有数，全部消成 0
            if (fabs(a[i][c]) > eps)// 如果非0 再操作，已经是 0就没必要操作了
                for (int j = n; j >= c; j -- )// 从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字，这样就能保证第一个数字是 a[i][0] -= 1*a[i][0];
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;// 这一行的工作做完，换下一行
    }

    if (r < n)// 说明剩下方程的个数是小于 n 的，说明不是唯一解，判断是无解还是无穷多解
    {// 因为已经是阶梯型，所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )// 
            if (fabs(a[i][n]) > eps)// a[i][n] 代表 b_i ,即 左边=0，右边=b_i,0 != b_i, 所以无解。
                return 2;
        return 1;// 否则， 0 = 0，就是r ~ n-1的方程都是多余方程
    }
    // 唯一解 ↓，从下往上回代，得到方程的解
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[j][n] * a[i][j];//因为只要得到解，所以只用对 b_i 进行操作，中间的值，可以不用操作，因为不用输出

    return 0;
}

当返回值为0时，按位输出a[i][n]。
当返回值为1时，表示有无穷多组解。
否则表示无解。

求组合数

给定三个整数a,b,p 其中p是质数，输出 $C^b_a$ mod p

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;
}
int C(int a,int b,int p)
{
    if(b>a)return 0;
    int res=1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i ++,j--)
    {
        res=(LL)res*j%p;
        res=(LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

答案：输出lucas(a,b,p)

满足条件的01序列

卡特兰数，组合计数
将 01 序列置于坐标系中，起点定于原点。若 0表示向右走，1表示向上走，表示从 (0,0)走到 (n,n)的路径。
题目限制：在函数 y = x 线及以下可行，输出方案数。

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;
}

int a = n * 2, 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;//乘上i的逆元

res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;//乘上n+1的逆元

cout << res << endl;

容斥原理

组合恒等式
$C^0_n + C^1_n + ...... + C^n_n = 2^n$
$C^1_k - C^2_k + C^3_k - C^4_k + \cdots$ $ +(-1)^{k-1} * C^k_k=1$
|Sp| 表示 1~n 中 p 的倍数的个数
$|Sp|=\left\lfloor\dfrac{n}{p}\right\rfloor$

博弈论

如果当前a1~an 之间异或起来不是0 的话一定有操作可以让其变成0