算法备忘录·数学知识

本文最后更新于 2022年11月21日 晚上

一直以来，没能系统学习算法，是我心中的痛；现在学了 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(Nlog⁡N)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(Nlog⁡log⁡N)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=p1c1∗p2c2∗⋯∗pkckN = 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=p1a1p2a2…pmamN=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{m}^{a_{m}}，则 ϕ(N)=N×p1−1p1×p2−1p2×…×pm−1pm\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 ~ NN 与 NN 互质的数的个数，被称为欧拉函数。
    • 容斥原理证明

计算欧拉函数

定义法

  • 时间复杂度 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(log⁡k)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=Ca−1b+Ca−1b−1C_a^b = C_{a-1}^b + C_{a-1}^{b-1}
  • 时间复杂度 O(N2)O(N^2)
    • 1≤b≤a≤20001\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!(b−a)!b!C_a^b=\frac{a!}{(b-a)!b!}。所以可以预处理阶乘，然后计算 Cab=fact[a]∗infact[b−a]∗infact[b]C_a^b=fact[a]*infact[b-a]*infact[b]
  • 时间复杂度 O(Nlog⁡N)O(N\log N)
    • 1≤b≤a≤1051\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 定理求组合数

  • 原理： Cab≡Ca mod pb mod p⋅Ca/pb/p(modp)C_a^b \equiv C_{a\bmod p}^{b \bmod p} \cdot C_{a/p}^{b/p} \pmod p
  • 时间复杂度： O(log⁡pN⋅p⋅log⁡p)O(\log_pN\cdot p \cdot \log p)
    • 1≤b≤a≤10181\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!(b−a)!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 的个数的序列的数量

容斥原理

  • 容斥原理：∣A1∪A2∪⋯∪Am∣=\left|A_{1} \cup A_{2} \cup \cdots \cup A_{m}\right|=
    ∑1≤i≤m∣Ai∣−∑1≤i<j≤m∣Ai∩Aj∣+∑1≤i<j<k≤m∣Ai∩Aj∩Ak∣−⋯+(−1)m−1∣A1∩A2∩⋯∩Am∣\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 博弈先手必胜，当且仅当 A1⊕A2⊕…⋯⊕An≠0A_1 \oplus A_2 \oplus …\cdots \oplus A_n \neq 0

有向图游戏

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

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

mex 运算

  • mex 运算：mex⁡(S)\operatorname{mex}(\mathrm{S}) 表示不属于集合 SS 的最小自然数，即 mex⁡(S)=min⁡{x∣x∉S∧x∈N}\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/算法备忘录·数学知识/
作者
Mobilis In Mobili
发布于
2021年11月22日
更新于
2022年11月21日
许可协议