算法备忘录·数学知识

本文最后更新于:2022年2月23日 上午

一直以来,没能系统学习算法,是我心中的痛;现在学了 y 总的算法基础课,做做笔记,希望能够有所收获。
这是第五节,数学知识。

尽管很多算法之前在离散数学中经常使用,但是从 OI 的视角来看,又是一种全新的感觉……

数学知识

质数

试除法判定质数

  • 时间复杂度 O(N)O(\sqrt{N})
  • 模板
1
2
3
4
5
6
7
bool isPrime(int x){
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ ) // 使用 x / i 效果最好,注意是 <=
if (x % i == 0)
return false;
return true;
}

试除法分解质因数

  • 时间复杂度 O(N)O(\sqrt{N})
  • 模板
1
2
3
4
5
6
7
8
void divide(int x){
for (int i = 2; i <= x / i; i ++ ){
int s = 0;
while (x % i == 0) x /= i, s ++;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
}

求素数

朴素筛法

  • 时间复杂度 O(NlogN)O(N\log N)
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
int primes[N], cnt; // primes[] 存储所有素数
bool st[N]; // st[x] 存储 x 是否被筛掉

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

埃氏筛

  • 时间复杂度 O(NloglogN)O(N\log\log N)
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
int primes[N], cnt; // primes[] 存储所有素数
bool st[N]; // st[x] 存储 x 是否被筛掉
void get_primes(int n){
for (int i = 2; i <= n; i ++ ){
if (!st[i]){
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i){
st[j] = true;
}
}
}
}

线性筛

  • 时间复杂度 O(N)O(N)
  • 模板
1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt; // primes[] 存储所有素数
bool st[N]; // st[x] 存储 x 是否被筛掉
voidget_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;
}
}
}

约数

试除法求所有约数

  • 模板
1
2
3
4
5
6
7
8
9
10
11
vector<int> get_divisors(int x){
vector<int> res;
for (int i = 1; i <= x / i; i ++ ){
if (x % i == 0){
res.push_back(i);
if (i ! = x / i) res.push_back(x / i);
}
}
sort(res.begin(), res.end());
return res;
}

int 范围内约数最多的个数约 1500 个

约数个数、约数之和

  • 如果 N=p1c1p2c2pkckN = p_1^{c_1} * p_2^{c_2} * \cdots * p_k^{c_k}
    • 约数个数: (c1+1)(c2+1)(ck+1)(c_1 + 1) * (c_2 + 1) * \cdots * (c_k + 1)
    • 约数之和: (p10+p11++p1c1)(pk0+pk1++pkck)(p_1^0 + p_1^1 + \cdots + p_1^{c_1}) * \cdots * (p_k^0 + p_k^1 + \cdots + p_k^{c_k})

欧几里得算法求最大公约数

  • 模板
1
2
3
int gcd(int a, int b){
return b ? gcd(b, a % b) : a
}

欧拉函数

  • N=p1a1p2a2pmamN=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{m}^{a_{m}},则 ϕ(N)=N×p11p1×p21p2××pm1pm\phi(N)=N \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \ldots \times \frac{p_{m}-1}{p_{m}}ϕ(N)\phi(N) 是 1 ~ NNNN 互质的数的个数,被称为欧拉函数。
    • 容斥原理证明

计算欧拉函数

定义法

  • 时间复杂度 O(N)O(\sqrt{N})
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
int phi(int x){
int res = x;
for (int i = 2; i <= x / i; i ++ ){
if (x % i == 0){
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);

return res;
}

筛法批量求欧拉函数

  • 时间复杂度 O(N)O(N)
    • 基于线性筛
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int primes[N], cnt; // primes[] 存储所有素数
int euler[N]; // euler[] 存储每个数的欧拉函数
bool st[N];


void get_eulers(int n){
euler[1] = 1; // 1 的欧拉函数值是 1
for (int i = 2; i <= n; i ++ ){
if (!st[i]){
primes[cnt ++ ] = i;
euler[i] = i - 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];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}

快速幂

快速幂算法

  • 快速求 mk(modp)m^k \pmod p,时间复杂度 O(logk)O(\log k)
  • 模板
1
2
3
4
5
6
7
8
9
int qmi(int m, int k, int p){
int res = 1 % p, t = m;
while (k){
if (k & 1) res = res * t % p;
t = t * t % p;
k >> = 1;
}
return res;
}

扩展欧几里得算法

  • 裴蜀定理:对于任意正整数 a,ba, b,一定存在整数 x,yx,y,使得 ax+by=(a,b)ax + by = (a, b)

扩展欧几里得算法

  • 模板
1
2
3
4
5
6
7
8
9
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;
}

高斯消元

高斯消元解线性方程组

  • 时间复杂度 O(N3)O(N^3)
  • 步骤
    • 枚举每一列 cc
    1. 找到绝对值最大的一行
    2. 将该行换到最上面
    3. 将该行第一个数变成 1
    4. 把下面所有行的第 cc 列变成 0
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 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 = i; // 找到绝对值最大的一行
}

if (fabs(a[t][c]) < eps) continue; //如果第 c 列是 0, 就直接考虑下一列

for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将该行换到最上面

for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将该行第一个数变成 1

for (int i = r; i <= n; i ++ )
if (fabs(a[i][c]) > eps)
for (int j = c; 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; // 有唯一解
}

组合数

递归法求组合数

  • 原理:Cab=Ca1b+Ca1b1C_a^b = C_{a-1}^b + C_{a-1}^{b-1}
  • 时间复杂度 O(N2)O(N^2)
    • 1ba20001\leq b\leq a\leq 2000
  • 模板
1
2
3
4
5
// 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;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

通过预处理逆元的方式求组合数

  • 原理:Cab=a!(ba)!b!C_a^b=\frac{a!}{(b-a)!b!}。所以可以预处理阶乘,然后计算 Cab=fact[a]infact[ba]infact[b]C_a^b=fact[a]*infact[b-a]*infact[b]
  • 时间复杂度 O(NlogN)O(N\log N)
    • 1ba1051\leq b\leq a\leq 10^5
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 快速幂模板
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] = fact[i - 1] * i;
infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

Lucas 定理求组合数

  • 原理: CabCamodpbmodpCa/pb/p(modp)C_a^b \equiv C_{a\bmod p}^{b \bmod p} \cdot C_{a/p}^{b/p} \pmod p
  • 时间复杂度: O(logpNplogp)O(\log_pN\cdot p \cdot \log p)
    • 1ba10181\leq b\leq a\leq 10^18
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 快速幂模板
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;
}


// 通过定义求组合数C(a, b)
int C(int a, int b, int p){
if (a < b) return 0;

LL x = 1, y = 1; // x是分子,y是分母
for (int i = a, j = 1; i <= b; i--, j ++ ){
x = (LL)x * i % p;
y = (LL)y * j % p;
}

return x * (LL)qmi(y, p - 2, p) % p;
}


int lucas(LL a, LL b, int p){
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p, p) % p;
}

分解质因数法求组合数

  • 需要求出组合数的真实值,而非对某个数的余数时,分解质因数的方式比较好用

  • 步骤

    1. 筛法求出范围内的所有质数
    2. 通过 Cab=a!(ba)!b!C_a^b=\frac{a!}{(b-a)!b!} 这个公式求出每个质因子的次数。
      • n!n!pp 的次数是 [np]+[np2]+[np3]+[\frac{n}{p}] + [\frac{n}{p^2}] + [\frac{n}{p^3}] + \cdots
    3. 高精度乘法将所有质因子相乘
  • 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int primes[N], cnt; // 存储所有质数
int sum[N]; //存储每个质数的次数
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;
}
}
}


// 求 n! 中素数 p 的次数
int get(int n, int p){
int res = 0;
while (n){
res += n / p;
n /= p;
}
return res;
}


// 高精度乘法
vector<int> mul(vector<int> a, b){
vector<int> c;
int t = 0;
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;
}


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]);

卡特兰数

  • 通项公式: Cn=C2nnn+1C_n = \frac{C_{2n}^n}{n+1}
  • 所有的卡特兰数问题经过一定的转换都可以还原成进出栈问题
  • 举例:给定 nn 个 0 和 nn 个 1,它们按照某种顺序排成长度为 2n2n 的序列,满足任意前缀中 00 的个数都不少于 1 的个数的序列的数量

容斥原理

  • 容斥原理:A1A2Am=\left|A_{1} \cup A_{2} \cup \cdots \cup A_{m}\right|=
    1imAi1i<jmAiAj+1i<j<kmAiAjAk+(1)m1A1A2Am\sum_{1 \leq i \leq m}\left|A_{i}\right|-\sum_{1 \leq i<j \leq m}\left|A_{i} \cap A_{j}\right|+\sum_{1 \leq i<j<k \leq m}\left|A_{i} \cap A_{j} \cap A_{k}\right|-\cdots+(-1)^{m-1}\left|A_{1} \cap A_{2} \cap \cdots \cap A_{m}\right|

    • 用组合数恒等式证明
  • 在应用时,对集合的枚举可以使用位运算来表示

博弈论

Nim 游戏

  • 给定 NN 堆物品,第 ii 堆物品有 AiA_i 个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。

  • 定理: Nim 博弈先手必胜,当且仅当 A1A2An0A_1 \oplus A_2 \oplus …\cdots \oplus A_n \neq 0

有向图游戏

  • 给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负。该游戏被称为有向图游戏。

  • 任何一个公平组合游戏都可以转化为有向图游戏。

mex 运算

  • mex 运算:mex(S)\operatorname{mex}(\mathrm{S}) 表示不属于集合 SS最小自然数,即 mex(S)=min{xxSxN}\operatorname{mex}(S)=\min \{x \mid x \notin S \wedge x \in \mathrm{N}\}

SG 函数

  • SG 函数:在有向图游戏中, 对于每个节点 xx, 设从 xx 出发共有 kk 条有向边, 分别到达节点 y1,y2,,yky_{1}, y_{2}, \cdots, y_{k}, 定义 SG(x)\mathrm{SG}(x)xx 的后继节点 y1,y2,,yky_{1}, y_{2}, \cdots, y_{k}SG\mathrm{SG} 函数值构成的集合再执行 mex(S)\operatorname{mex}(S) 运算的结果,即:

SG(x)=mex(SG(y1),SG(y2),,SG(yk))\mathrm{SG}(x)=\operatorname{mex}(\mathrm{SG}(y_1), \mathrm{SG}(y_2), \cdots, \mathrm{SG}(y_k))

有向图游戏的和

  • G1,G2,,GmG_{1}, G_{2}, \cdots, G_{m}mm 个有向图游戏。定义有向图游戏 GG,它的行动规则是任选某个有向图游戏 GiG_{i},并在 GiG_{i} 上行动一步。GG 被称为有向图游戏 G1,G2,,GmG_{1}, G_{2}, \cdots, G_{m} 的和。
  • 有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和, 即:

SG(G)=SG(G1)SG(G2)SG(Gm)\mathrm{SG}(G)=\mathrm{SG}\left(G_{1}\right) \oplus \mathrm{SG}\left(G_{2}\right) \oplus \cdots \oplus \mathrm{SG}\left(G_{m}\right)

有向图游戏必胜

  • 有向图游戏的某个局面必胜,当且仅当该局面对应节点的SG函数值大于 0;

  • 有向图游戏的某个局面必败*,当且仅当该局面对应节点的SG函数值等于** 0。

  • 解释:

    • 非 0 可以走向 0
    • 0 只能走向非 0
  • 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int s[N], f[N];  // s[]表示每次能够拿取石子数的集合;f[] 记录石子数为 x 堆的 sg 函数值

memset(f, -1, sizeof f);


// 记忆化搜索
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];
if (x >= sum) S.insert(sg(x - sum));
}

// mex(x)
for (int i = 0; ; i ++ )
if (!S.count(i))
return f[x] = i;
}


// 把 n 堆石子看成 n 个独立的有向图 G,把各个有向图结果做异或得到答案
int x, res = 0;
for (int i = 0; i < n; i ++ )
{
cin >> x;
res ^= sg(x);
}


算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析


算法备忘录·数学知识
https://justloseit.top/算法备忘录·数学知识/
作者
Joker
发布于
2021年11月22日
更新于
2022年2月23日
许可协议