1、质数

//1、试除法
bool is_prime(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n; i ++)
        if (n % i == 0)
            return false;
    return true;
}
//2、试除法优化
/*如果d/n能整除，那么n/d / n也能整除。比如n = 12, 3和4都是他的约数，n的约数都是成对出现的  。在枚举的时候我们可以只枚举没对较小的一个就可以了。
*/
bool is_prime(int n)
{
    if (n < 2) return false;
    //i <= n / i 时间复杂度根号n
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0)
            return false;
    return true;
}

2、分解质因数

bool divide(int n)
{
    //i <= n / i 时间复杂度根号n
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0)//i一定是质数
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            printf("%d %d\n", i, s);//对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
        }
    //每个质因数的底数和指数，每个底数和指数占一行
    if (n > 1) printf("%d %d\n", n, 1);
    puts("");
}

3、筛质数

1～n中质数有n/ln(n)个质数，按顺序删除每个数的倍数，最后剩下的就是质数。

int primes[N], cnt;//primes[]存储所有素数
bool st[N];//st[x]存储x是否被筛掉
//朴素做法
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++){//从2开始枚举
        
        if (!st[i])primes[cnt ++ ] = n;//当前数没有被筛过，则是个质数
        for (int j = i + i; j <= n; j +=i) //j = i + i，将n的倍数删除掉
            st[j] = true;//标记为true
    }
}
 
//埃式筛法-O(nloglogn)
void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]){ 
            prime[cnt++] = i;
            for(int j = i; j <= n; j += i)
                st[j] = true;
        }
    } 
}
 
//线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了
//算法核心：x仅会被其最小质因子筛去
void get_prime(int x) {
    for(int i = 2; i <= x; i++) {
        if(!st[i]) prime[cnt++] = i;//找到质数
        for(int j = 0; prime[j] <= x / i; j++) {//从0开始找j倍数
            //对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
            st[prime[j]*i] = true;//倍数直接标记
            if(i % prime[j] == 0) break;
            /*
            1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子
            2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
            */
        }
    }
} 

4、试除法求约数

1、从小到大枚举所有约数

2、只枚举每一对约数较小的

3、如果i != n / i,才加进去

#include <iostream>
#include <algorithm>
#include <vector>//存一个数所有约数
 
using namespace std;
 
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);//可能会出现n = i*i,两个余数相同的情况，所以需要判断一下
        }
    //最后将约数排个序
    sort(res.begin(), res.end());
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    
    while (n --)
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);//dedaox所有的约数
        //循环遍历输出x的约数
        for (auto t : res) cout << t << ' ';
        cout << endl;
    }
    return 0;
}

5、约数之和

实际上就是n的所有约数个数加到一块，如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

#include <iostream>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
typedef long long LL;
 
const int mod = 1e9 + 7;
 
int main()
{
    int n;
    cin >> n;
    
    //定义哈希表存所有底数和指数
    unordered_map<int, int> primes;
    
    while (n --)
    {
        int x;
        cin >> x;
        //遍历求x质因数
        for (int i = 2; i <= x / i; i ++)
            while (x % i == 0)
            {
                x /= i;
                //i的质因数指数+1
                primes[i] ++ ;//存质因数指数
            }
        //判断如果x>1说明x是一个比较大的质因数
        if (x > 1) primes[x] ++;//将剩下的质因数加上就好了
    }
    
    //枚举所有的质因数
    LL res = 1;
    //带入求和公式：
    for (auto prime : primes) 
    {
        //1、枚举每一个质数
        int p = prime.first, a = prime.second;//p表示质数的底数，a表示质数的底数
        LL t = 1;//t来存每一部分的总和
        //2、先求P的0次方+...+P的a次方,然后每次对t进行操作： t = p * t + 1
        //t = 1,p + 1;第二次t = 2,p^2 + p + 1;第a次p^a +...+1
        while (a --) t = (t * p + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;//得到结果
    
    return 0;
}

6、求最大公约数（欧几里得）

如果d能整除a,d能整除b，则d能整除a+b，也能整除(ax + by);则(a, b)的最大公约数 = (b, a mod b);

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;//b如果不是0返回a%b最大公约数，如果为0则返回a
}

7、求欧拉函数

筛法求欧拉函数

1、如果这个数是质数，1～p-1都是质数

2、如果i % primes[j] == 0,说明i是p[j]的质因子则有：

3、如果i % primes[j] ！= 0，pj是(i*pj)的最小质因子，则有：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    
    while (n --)
    {
        int a;
        cin >> a;
        int res = a;//答案用res表示
        //分解质因数
        for (int i = 2; i <= a / i; i ++)
            if (a % i == 0)
            {
                res = res / i * (i - 1);//等价于i*(1-1/i)
                while (a % i == 0) a /= i; 
            }
        if (a > 1) res = res / a*(a - 1);//如果还没除完，再除一次
        
        cout << res << endl;    
    }
    
    return 0;
}

//筛选法求欧拉函数

//primes存的每一个质数, cnt存质数下标
int primes[N], cnt;
//欧拉函数
int phi[N];
bool st[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;//如果这个数是质数，1～p-1都是质数
        }
        //从小到大枚举所有质数
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;//标记已经筛过
            if (i % primes[j] == 0) //break;//一个优化变成线性
            {
                //i % primes[j] == 0,说明i是p[j]的质因子
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            //如果i % primes[j] ！= 0，pj是(i*pj)的最小质因子
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    
    LL res = 0;//定义总和
    for (int i = 1; i <= n; i ++) res += phi[i];//求总和
    return res;
}

8、快速幂

快速求出来a^k mod p的结果

int qmi(int a, int k, int p)
{
    int res = 1;//答案
    while (k)
    {
        //第一次迭代从a^0开始,1开始
        if (k & 1) res = (LL) res * a % p;//如果当前k的末位是1，则是第一次迭代
        //把k的末位删除
        k >>= 1;
        //把a变成下一个
        a = (LL)a * a % p;//a平方一下
        
    }
    return res;//返回res
}

//Example-求逆元
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
//a^k % p
int qmi(int a, int k, int p)
{
    int res = 1;//答案
    while (k)
    {
        //第一次迭代从a^0开始,1开始
        if (k & 1) res = (LL) res * a % p;//如果当前k的末位是1，则是第一次迭代
        //把k的末位删除
        k >>= 1;
        //把a变成下一个
        a = (LL)a * a % p;//a平方一下
        
    }
    return res;//返回res
}
 
int main()
{
    int n;
    //读入数据比较多yong scanf
    scanf("%d", &n);
    while (n --)
    {
        int a, p;
        scanf ("%d%d", &a, &p);
        
        int res = qmi(a, p - 2, p);//费马定理，求出结果
        if (a % p) printf("%d\n", res);//说明d不是p的倍数，输出res
        //如果p = 2比较特殊，是0次方，需要特判
        else printf("impossible\n");//d是p的倍数说明一定无解
    }
    
    return 0;
}

9、扩展欧几里得算法-线性同余方程

概念：给定a, b, m，求整数x,使得： ax = b(mod m)；

举例：2x = 3 (mod 6) 无解

          4x = 3 (mod 5) :4*某一个数 同于于 4*某一个数/5的余数是3. x可以等于 2，7等。

等式变形：

ax = b(mod m) 等价于 存在一个整数y属于z，使得 ax = m*y + b  --> ax - my = b --> y` = y, ax + my` = b;

注意：该式子能成立的条件是b能整除(a,m)最大公约数，(a, m) | b, 那么就有解，否则一定无解。
 

int exgcd(int a, int b, int &x, int &y)
{
    //return b ? gcd(b, b % a) : a;
    if (!b) //如果b = 0,ax + by = a
    {
        //得到一组解
        x = 1, y = 0;
        return a;//如果b = 0,返回a
    }
    //by + (a mod b)x = (a, b)最大公约数d
    int d = exgcd(b, a % b, y, x);//存下最大公约数,翻转了一下
    //a mod b = a - (a / b)下取整 * b带入
    //by + (a - (a / b)下取整 * b)x = d;
    //展开整理：ax + b (y - (a/b)*x)
    //得到a的系数不变为a,y的系数变成：y - (a/b)*x
    y -= a / b * x;
    
    return d;
}

10、高斯消元

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];//存矩阵
 
int gauss()
{
    int c, r;//定义行和列
    //1、从第0行第0列开始，找到绝对值最大的一行
    for (c= 0, r = 0; c < n; c ++)
    {
        int t = r;
        for (int i = r; i < n; i ++)
            //如果找到绝对值比较大的一列，fabs表示绝对值函数
            if (fabs(a[i][c] > fabs(a[t][c])))
                t = i;//换成当前列
        //因为值是double类型，所以为了防止出现精度问题我们需要特判一下
        if (fabs(a[t][c]) < eps) continue;//fabs是返回浮点数绝对值，如果当前是0，返回continue
        
        //2、把当前绝对值最大一行换到最上面去
        for (int i= c; i <= n; i ++) swap(a[t][i], a[r][i]);
        //3、将换上去的那行第一个数化成1
        //从最后一个开始换
        for (int i = n; i >= c; i --) a[r][i] /= a[r][c];
        //4、将下面所有行的当前列，消成0
        for (int i = r + 1; i < n; i ++)
            if (fabs(a[i][c]) > eps)//从第二列开始，如果第一个数大于零才进行消0操作
                for (int j = n; j >= c; j --)//把第一行通过乘除操作，是的第一行第一个数与第二行第一个数相同，然后进行相减
                    a[i][j] -= a[r][j] * a[i][c];//a[r][j] * a[i][c]:第一行的数*第i行第一个数的值
        //操作完记得 r ++
        r ++;
    }
    if (r < n)//5、结果不到n个，可能存在无解或者无穷多个解
    {
        //如果出现0 = 非零情况，则无解
        for (int i = r; i < n; i ++) 
            if (fabs(a[i][n]) > eps)//每行最后一个存在>0的结果，即0 = 非零情况，则无解
                return 2;//无解
        return 1;//否则有无穷多种解
    }
    //6、找到三角结构，就互相消元。倒着把方程消一遍,把除了第一个数以外后面的数消成0
    for (int i = n - 1; i >= 0; i --)
        for (int j = i + 1; j < n; j ++)
            //从第最后一个i个开始消
            //把当前这方程除了xi这个系数之外所有系数消成0，减去他的系数*他的值
            a[i][n] -= a[i][j] * a[j][n];//a[j][n]是xj的值
    
    
    return 0;//如果r = n,则只有唯一解
}
 
int main()
{
    cin >> n;//n行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)//t = 0唯一解
    {
        for (int i = 0; i < n; i ++) printf("%.2f\n", a[i][n]);
    }//t = 1无穷多种解
    else if (t == 1) puts("Infinite group solutions");
    //t = 2无解 
    else puts("No solution");
    
    return 0;
}

11、求组合数

//递归法求组合数
// 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;//如果是第一个数0，则标记1
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;////按照公式来

//
/*首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元*/
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;
}

12、博弈论

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

方法：找奇数台阶，如果奇数台阶异或！=0,则胜利。

充要条件：所有奇数级台阶所有石子异或起来不等于0.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    int res = 0;
    
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++)
    {
        int x;
        scanf ("%d", &x);
        if (i % 2) res ^= x;//所有奇数级台阶所有石子异或起来不等于0.
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}

Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：找到集合当中不存在的最小自然数。
mex(S) = min{x}, x属于自然数，且x不属于S

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。SG(终点)=0,存在y1, y2, ... ,yn的局面。图的最后一个点(第二条路径)即终点定义为0，终点前一个点不存在最小自然数则为1，往后一个数不存在最小自然数除了0和1，那么就是2了，如此递推，最开始那个不存在最小自然数为3。

结论：SG = 0,必败，SG ！= 0必败。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
 
using namespace std;
 
const int N = 110, M = 10010;
 
int n, m;
int s[N], f[M];//s表示谁的个数，f表示SG的值
 
//求sg
int sg(int x)
{
    //记忆化搜索--优化
    if (f[x] != -1) return f[x];//如果每个状态都被算过直接返回结果
    
    //哈希表存他所有可以到的局面
    unordered_set<int> S;
    for (int i = 0; i < m; i ++)
    {
        //当前数的个数
        int sum = s[i];
        //如果当前个数>=sum，才可以取这些数
        if (x >= sum) S.insert(sg(x - sum));
    }
    //判断当前集合当中不存在的点
    for (int i = 0; ; i ++)
        if (!S.count(i))//如果当前数不存在，当前的值就是i
            return f[x] = i;
}
 
int main()
{
    cin >> m;//读入m个数
    //输入操作
    for (int i = 0; i < m; i ++) cin >> s[i];
    cin >> n;//读入n,求的SG，每堆的个数
    
    memset(f, -1, sizeof f);//用记忆化搜索
    
    //求每一堆的个数
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}