算法备忘录·数学知识

本文最后更新于 2024年5月15日凌晨

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

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

数学知识

质数

试除法判定质数

时间复杂度 $O(\sqrt{N})$
模板

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(\sqrt{N})$
模板

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(N\log N)$
模板

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\log\log N)$
模板

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)$
模板

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

约数

试除法求所有约数

模板

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 = p_1^{c_1} *p_2^{c_2}* \cdots * p_k^{c_k}$ $N = p_{1}^{c_{1}} * p_{2}^{c_{2}} * \dots * p_{k}^{c_{k}}$
- 约数个数： $(c_1 + 1) *(c_2 + 1)* \cdots * (c_k + 1)$
- 约数之和： $(p_1^0 + p_1^1 + \cdots + p_1^{c_1}) *\cdots* (p_k^0 + p_k^1 + \cdots + p_k^{c_k})$

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

模板

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

欧拉函数

$N=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{m}^{a_{m}}$ $N = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{m}^{a_{m}}$ ，则 $\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) = N \times \frac{p _{1} - 1}{p _{1}} \times \frac{p _{2} - 1}{p _{2}} \times \dots \times \frac{p _{m} - 1}{p _{m}}$ 。 $\phi(N)$ $ϕ (N)$ 是 1 ~ $N$ $N$ 与 $N$ $N$ 互质的数的个数，被称为欧拉函数。
- 容斥原理证明

计算欧拉函数

定义法

时间复杂度 $O(\sqrt{N})$
模板

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)$
- 基于线性筛
模板

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

快速幂

快速幂算法

快速求 $m^k \pmod p$ ，时间复杂度 $O(\log k)$
模板

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, b$ ，一定存在整数 $x,y$ ，使得 $ax + by = (a, b)$

扩展欧几里得算法

模板

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(N^3)$
步骤
- 枚举每一列 $c$
1. 找到绝对值最大的一行
2. 将该行换到最上面
3. 将该行第一个数变成 1
4. 把下面所有行的第 $c$ 列变成 0
模板

// 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; // 有唯一解
}

组合数

递归法求组合数

原理： $C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$
时间复杂度 $O(N^2)$ $O (N^{2})$
- $1\leq b\leq a\leq 2000$
模板

// 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;

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

原理： $C_a^b=\frac{a!}{(b-a)!b!}$ 。所以可以预处理阶乘，然后计算 $C_a^b=fact[a]*infact[b-a]*infact[b]$
时间复杂度 $O(N\log N)$ $O (N lo g N)$
- $1\leq b\leq a\leq 10^5$
模板

// 快速幂模板
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 定理求组合数

原理： $C_a^b \equiv C_{a\bmod p}^{b \bmod p} \cdot C_{a/p}^{b/p} \pmod p$
时间复杂度： $O(\log_pN\cdot p \cdot \log p)$ $O (lo g_{p} N \cdot p \cdot lo g p)$
- $1\leq b\leq a\leq 10^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;
}


// 通过定义求组合数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. 通过 $C_a^b=\frac{a!}{(b-a)!b!}$ $C_{a}^{b} = \frac{a !}{( b - a ) ! b !}$ 这个公式求出每个质因子的次数。
  - $n!$ 中 $p$ 的次数是 $[\frac{n}{p}] + [\frac{n}{p^2}] + [\frac{n}{p^3}] + \cdots$
3. 用高精度乘法将所有质因子相乘
模板

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

卡特兰数

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

容斥原理

容斥原理： $\left|A_{1} \cup A_{2} \cup \cdots \cup A_{m}\right|=$
$\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 游戏

给定 $N$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。
定理： Nim 博弈先手必胜，当且仅当 $A_1 \oplus A_2 \oplus …\cdots \oplus A_n \neq 0$

有向图游戏

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

mex 运算

mex 运算： $\operatorname{mex}(\mathrm{S})$ 表示不属于集合 $S$ 的最小自然数，即 $\operatorname{mex}(S)=\min \{x \mid x \notin S \wedge x \in \mathrm{N}\}$ 。

SG 函数

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

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

有向图游戏的和

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

$\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
模板

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