1.质数

在大于1的整数，如果质包含1和本身这两个约数，就称之为素数/质数。

1.质数的判定（试除法）

优化后的：

#include<iostream>
#include<algorithm>

using namespace std;

bool is_prime(int n)
{if(n < 2) return false;for(int i = 2;i <= sqrt(n); i++)if(n % i == 0)return false;return true;
}

int main()
{int n;scanf("%d", &n);if(is_prime(n))printf("Yes");elseprintf("No");return 0;
}

2.分解质因数

分解质因数（试除法）

从小到大枚举所有的数。

n中最多只包含一个大于sqrt(n)的质因子

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

void divide(int n)
{for(int i = 2;i <= n / i; i++)if(n % i == 0)//一定是质数{int s = 0;while(n % i == 0){n /= i;s++;}printf("%d %d", i, s);}if(n > 1)printf("%d %d\n", n, 1);puts("");
}

int main()
{int n;scanf("%d", &n);while(n--){int x;scanf("%d", &x);divide(x);}return 0;
}

868.筛质数：

埃氏筛法：O(nloglogn)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{for(int i = 2;i <= n; i++){if(!st[i]){primes[cnt++] = n;for(int j = i+1;j <= n; j+= i)st[j] = true;}}
}

int main()
{int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

线性筛法：n只会被最小质因子筛掉

i%pj==0 pj一定是i的最小质因子，pj一定是pj*i的最小质因子
i%pj!=0 pj一定小于i的所有质因子，pj也一定是pj*i的最小质因子
对于一个合数x，假设pj是x的最小质因子，当i枚举到x/pj时

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int primes[N], cnt;
bool st[N];

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++){st[primes[j] * i] = true;if(i % primes[j] == 0)//primes[j]一定是i的最小因子break;}}
}

int main()
{int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

2.约数

试除法求约数：

#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++){if(n % i == 0){res.push_back(i);if(i != n/i) res.psuh_back(n / i);}}sort(res.begin(), res.end());return res;
}

int main()
{int n;scanf("%d", &n);while(n--){int x;cin >> x;auto res = get_divisors(x);for(auto t : res) cout << t << ' ';cout << endl;}return 0;
}

870.约数的个数

给定n个正整数ai，请你输出这些数的乘积的约数个数。答案对1e9+7取模

代码

#include<iostream>
#include<algorithm>
#include<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;for(int i = 2;i <= x / i; i++){while(x % i == 0){x /= i;primes[i]++;}}if(x > 1) primes[x]++;}LL res = 1;for(auto prime : primes) res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

871.约数之和

#include<iostream>
#include<algorithm>
#include<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;for(int i = 2;i <= x / i; i++)while(x % i == 0){x /= i;primes[i]++;}if(x > 1) primes[i]++;}LL res = 1;for(auto prime: primes){int p = prime.first, a = prime.second;LL t = 1;while(a--)t = (t * p + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}

欧几里得算法

又叫辗转相除法

最大公约数

#include<iostream>

using namespace std;

int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}

int main()
{int n;scanf("%d", &n);while(n--){int x;scanf("%d", &x);printf("%d\n", gcd(a, b));}return 0;
}

3.欧拉函数

873.欧拉函数：

uTools_1689908691737

给定n个正整数ai，请你求出每一个数的欧拉函数。

1~n中与n互质的数的个数

容斥原理：

从1~N争取去掉p1，p2，..., pk的所有倍数
加上所有pi*pj的倍数
再减去pi*pj *pz的倍数
再加上pi *pj *pz *pm的倍数

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{int n;cin >> n;while(n--){int x;cin >> x;int res = a;for(int i = 2;i <= a / i; i++)if(a % i == 0){res = res / a * (i - 1);while(a % i == 0) a /= i;}if(a > 1) res = res / a * (a - 1);cout << res << endl;}return 0;
}

874.筛法求欧拉函数

线性筛法：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

int primes[N], cnt;
int phi[N];
int st[N];

LL get_eulers(int n)
{for(int i = 2;i <= n; i++){if(!st[i]){primes[cnt++] = i;}for(int j = 0;primes[j] <= n / i; j++){st[primes[j] * j] = true;if(i % primes[i] == 0){phi[primes[j] * i] = primes[j] * phi[i];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;
}

int main()
{int n;cin >> n;cout << get_eulers(n) << endl;return 0;
}

欧拉定理

欧拉定理有以下两种说法：

在任何一个规则球面地图上，用R记区域个数，V记顶点个数，E记边界个数，则R+V-E=2。
aφ(n)≡1(mod n)，其中，a aa与n nn均为正整数，且两者互质。

欧拉定理的证明过程如下：

设[1，n]内与n互质的数集为X，每个元素为x。
设f=F(n)，则X的元素个数为f。
设R=(a^f) % n，因为a与n互质，所以a^f与n互质，所以R属于[1，n)。
根据欧拉定理，a1、a2、...、an为n的一个完全剩余系，因此，对任意两个不同的x元素，其(ax) % n也不同。
因为a与x都与n互质，所以ax与n互质，根据定理，(ax)%n与n互质。
综上所述，(a*x) % n是[1，n)范围内f个两两不同且均与n互质的数，因此它们就是数集X。

4.快速幂

875.快速幂：

给定n组ai，bi，pi，对于每组数据，求出ai的bi次方 mod pi的值。

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

int n;

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()
{scanf("%d", &n);while(n--){int a, k, p;scanf("%d%d%d", &a, &k, &p);printf("%d\n", qmi(a, k, p));}return 0;
}

876.快速幂求逆元：

给定n组ai，pi，其中pi是质数，求ai模pi的乘法逆元，若逆元不存在则输出impossible

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;
int n;

int qmi(int a, int k, int p)
{int res = 0;while(k){if(k & 1) res = (LL)res * a % p;k >>= 1;a = (LL)a * a % p;}return res;
}

int main()
{scanf("%d", &n);while(n--){int a, p;scanf("%d%d%d", &a, &p);int res = qmi(a, p - 2, p);if(a % p) printf("%d\n", res);else puts("impossible");}return 0;
}

5.扩展欧几里得算法

877.扩展欧几里得算法：

裴蜀定理：

有一对正整数a，b，那么存在整数x，y，使得ax+by=(a, b)

#include<iostream>
#include<algorithm>

using namespace std;

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

int main()
{int n;scanf("%d", &n);while(n--){int a, b, x, y;scanf("%d%d", &a, &b);exgcd(a, b, x, y);printf("%d %d", x, y);}return 0;
}

878.线性同余方程

给定n组数据ai，bi，mi，对于每组数求出一个xi。使满足ai * xi 恒等于 bi(mod mi)，如果不存在，就输出impossible。

ax - by = m，此处的m就是余数。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;

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

int main()
{int n;scanf("%d", &n);while(n--){int a, b, m;scanf("%d%d%d", &a, &b, &m);int x, y;int d = exgcd(a, m, x, y);if(b % d) puts("impossible");else printf("%d\n", (LL)x * (b / d) % m);}return 0;
}

2 3 6

4 3 5

6.中国剩余定理

m1, m2, ..., mx两两互质

x 恒等于 a1(mod m1)

x 恒等于 a2(mod m2)

x 恒等于 a3(mod m3)

......

x 恒等于 a4(mod m4)

M = m1m2...mx

Mi = M / mi Mi-1表示Mi模mi的逆

204.表达整数的奇怪方式

给定2n个整数a1,a2.....,an和m1,m2,.....,mn,求一个最小的整数x，满足任意i∈[1, n],x恒等于mi mod ai

待完成，敬请期待~！

7.高斯消元

883.高斯消元解线性方程组

输入一个包含n个方程n个未知数的线性方程组。

方程组中系数为实数。

求解这个方程组。

解的形式：无解、无穷多解、唯一解。

高斯消元，线性代数的初等变换

把某一行乘以一个非零的数
交换某两行
把某一行的若干倍加到另一行上去

判断解：

完美阶梯型——唯一解
0 = 非零——无解
0 = 0 ——无穷多组解

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

int n;
double a[N][N];

int gauss()
{int 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 = 1;if(fabs(a[t][c]) < eps) continue;for(int i = c;i <= n; i++) swap(a[t][i], a[r][i]);for(int i = n;i >= n; i--) a[r][i] /= a[r][c];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];r++;}if(r < n){for(int i = r;i < n; i++)if(fabs(a[i][n]) > eps)return 2;//无解return 1;//有无穷多解}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 < 0; 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) puts("Infinate group solutions");else puts("No solution");return 0;
}

884.高斯消元解异或线性方程组

8.组合计数

885.求组合数I：

给定n组询问，每组询问给定两个整数a，b，请你输出Cab mod (1e9 + 7)

3 1

5 3

2 2

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2010, mod = 1e9 = 7;

int c[N][N];

void init()
{for(int i = 0;i < N; i--)for(int j = 0;j <= i; j++)if(!j) c[i][j] = 0;else c[i][j] = c[i-1][j] + c[i-1][j-1] % mod;
}

int main()
{init();int n;scanf("%d", &n);while(n--){int a, b;scanf("%d%d", &a, &b);printf("%d\n", c[a][b]);}
}

886.求组合数II：

给定n组询问，每组询问给定两个整数a，b，请你输出Cab mod (1e9 + 7)

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, mod = 1e9 + 7;

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

int main()
{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;}int n;scanf("%d", &n);while(n--){int a, b;scanf("%d%d", &a, &b);printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);}return 0;
}

887.求组合数III：

5 3 7

3 1 5

6 4 13

卢卡斯定理：

Lucas定理是用来求c(n,m) mod p，p为素数的值1。

Lucas定理的推导过程为：首先需要这个算式：x^f mod p，然后(1+x)n= (1+x)t * (1+x)(n-t) mod p，所以得(1+x)^(t*(p-1)) mod p=11。

Lucas定理的定律为：令n=sp+q，m=tp+r（0≤q，r≤p-1），则C(n,m)=C(s,t)C(p-1,q)C(p-1,r)/C(p-1,t)1。

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int 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)
{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 < b && b < p) return C(a, b);return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main()
{int n;scanf("%d", &n);while(n--){LL a, b;scanf("%d%d", &a, &b);scanf("%d", &p);cout << lucas(a, b) << endl;}return 0;
}

888.求组合数IV：

高精度运算

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int N = 5010;

int primes[N], cnt;
bool st[N];

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++){st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}

void get(int n, int p)
{int res = 0;while(n){res += n / p;n /= p;}return res;
}

vector<int> mul(vector<int> a, int b)
{vector<int> c;for(int i = 0;i < a.size(); i++){t += a[i] * b;c.push_back(t % 10);t /= 10;}while(t){c.push_back(t % 10);t /= 10;}return c;
}

int main()
{int a, b;scanf("%d%d", &a, &b);get_primes(a);for(int i = 0;i < cnt; i++){int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a - b, p);}vector<int> res;res.push_back(1);for(int i = 0;i < cnt; i++)for(int j = 0;j < sum[i]; j++)res = mul(res, primes[i]);for(int i = res.size() - 1;i >= 0; i--)printf("%d", res[i]);puts("");return 0;
}

#pragram GCC optimize(2)

889.满足条件的01序列

给定n个0和n个1，他们按照某种顺序排成长度为2n的序列，求它们能排列组合的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少。

输出答案对1e9+7取模。

0：往右走一格

1：往上走一格

卡特兰数：

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图（1692-1763）和比利时的数学家欧仁·查理·卡塔兰（1814–1894）的名字来命名，其前几项为（从第零项开始）：1、1、2、5、14、42、132、429、1430、4862，...1。

卡特兰数在计算机专业中比较重要，有一些具体的应用实例。这篇文章主要分三部分：卡特兰数递归式的含义解释、卡特兰数表达式的证明过程、卡特兰数的计算机中的应用

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e9 + 7;

typedef long long LL;

int qmi(int a, int b, 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 main()
{int n;scanf("%d", &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);cout << res << endl;return 0;
}

9.容斥原理

890.能被整除的数：

给定一个整数n和m个不同的质数p1，p2，....,pm

请你求出1~n中能被p1，p2，...,pm中的至少一个数整除的整数有多少个。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int n, m;
int p[N];

int main()
{scanf("%d%d", &n, &m);for(int i = 0;i < m; i++)scanf("%d", &p[i]);int res = 0;for(int i = 1;i < 1 << m; i++){int t = 1, cnt = 0;for(int j = 0;j < m; j++)if(i >> j & 1){cnt++;if((LL)t * p[j] > n){t = -1;break;}t *= p[j];}if(t != -1){if(cnt % 2)res += n / t;elseres -= n / t;}}printf("%d", res);return 0;
}

10.简单博弈论

891.Nim游戏：

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。 NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

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

/*

先手必胜状态，可以是某一个必败状态
先手必败状态，走不到任何一个必败状态

*/

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 101;

int a[N][N];

int main()
{int n;int res;scanf("%d", &n);while(n--){int x;scanf("%d", &x);res ^= x;}if(res) puts("Yes");else puts("No");return 0;
}

由两名玩家交替行动；在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；不能行动的玩家判负；则称该游戏为一个公平组合游戏。 NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

892.台阶Nim游戏：

893.集合Nim游戏：

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)。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

int sg(int x)
{if(f[x] != -1) return f[x];unodered_set<int> S;for(int i = 0;i < m; i++){int sum = s[i];if(x >= sum) S.insert(sg(x - sum));}for(int i = 0;; i++)if(!S.count(i))return f[x] - i;
}

int main()
{scanf("%d", &n);for(int i = 0;i < m; i++)scanf("%d", &s[i]);scanf("%d", &m);memset(f, -1, sizeof(f));int res = 0;for(int i = 0;i < n; i++){int x;scanf("%d", &x);res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}