AcWing 数学知识章节笔记

数学这一章题很多，但真正要背下来的核心模板并不算多。关键在于分清“结论”“适用条件”和“代码实现”。

本章核心模板

质数 / 约数 / gcd

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

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

线性筛

1
2
3
4
5
6
7
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
long long qmi(long long a, long long k, long long p) {
    long long res = 1 % p;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

扩展欧几里得

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

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
        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++;
    }
    return r;
}

组合数

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

本章题目与题解要点

质数

约数

欧拉函数

快速幂

扩展欧几里得

中国剩余定理

高斯消元

求组合数

容斥原理

博弈论

这一章怎么复习

  1. 先记熟 qmi、gcd、exgcd 三个模板。
  2. 再做 868、874、878、886 这四题，补齐筛法、欧拉函数、线性同余和组合数。
  3. 最后回头处理 204、884、893 这类更偏技巧的题。

返回导航