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");
else
printf("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.欧拉函数：
给定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
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
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：
3
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;
else
res -= 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;
}
