本文作者：yxc

来源: AcWing

原文地址：https://www.acwing.com/blog/content/406/

常用算法模板——数学知识

试除法判定质数

1
2
3
4
5
6
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;
    return true;
}

试除法分解质因数

1
2
3
4
5
6
7
8
9
10
void divide(int x) {
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) x /= i, s++;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

朴素筛法求素数

1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt = 0;  // primes[]存储所有素数，cnt为素数个数
bool st[N] = {false};    // st[x]存储x是否被筛掉

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        primes[cnt++] = i;
        // 筛去所有 i 的倍数
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

线性筛法求素数

1
2
3
4
5
6
7
8
9
10
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int p : primes) {
            if (p * i > n) break;
            st[p * i] = true;
            if (i % p == 0) break;
        }
    }
}

试除法求所有约数

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

约数个数和约数之和

1
2
3
如果 N = p1^c1 * p2^c2 * ... * pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

欧几里得算法

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

求欧拉函数

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

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int primes[N], cnt = 0;  // primes[]存储所有素数，cnt为素数个数
bool st[N] = {false};    // st[x]存储x是否被筛掉
int euler[N];            // 存储每个数的欧拉函数

void get_eulers(int n) {
    euler[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);
        }
    }
}

快速幂

1
2
3
4
5
6
7
8
9
int QuickPow(int a, int b, int m) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

高斯消元

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

        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 + 1; i < n; i++)  // 用当前行将下面所有的列消成0
            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;  // 有唯一解
}

递归法求组合数

1
2
3
4
5
6
7
// 计算 C(a,b)%p
int ans[1000][1000] = {0};
int C(int a, int b, int p) {
    if (b == 0 || a == b) return 1;
    if (ans[a][b] != 0) return ans[a][b];
    return ans[a][b] = (C(a - 1, b) + C(a - 1, b - 1)) % p;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
//如果取模的数是质数，可以用费马小定理求逆元
int QuickPow(int a, int b, int m) {  // 快速幂模板
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

// 预处理阶乘的余数和阶乘逆元的余数
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] * QuickPow(i, mod - 2, mod) % mod;
}

Lucas 定理

若 p 是质数，则对于任意整数 1 <= m <= n 有：

C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

1
2
3
4
int lucas(int a, int b, int p) {
    if (a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

卡特兰数

1
2
3
给定 n 个 0 和 n 个 1，它们按照某种顺序排成长度为 2n 的序列，
满足任意前缀中 0 的个数都不少于 1 的个数的序列的数量为：
Cat(n) = C(2n, n) / (n + 1)

NIM 游戏

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

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

相关内容