跳转至

数学基础知识

符号

整除/同余理论常见符号

  1. 整除符号：\(x\mid y\)，表示 \(x\) 整除 \(y\)，即 \(x\) 是 \(y\) 的因数。
  2. 取模符号：\(x\bmod y\)，表示 \(x\) 除以 \(y\) 得到的余数。
  3. 互质符号：\(x\perp y\)，表示 \(x\)，\(y\) 互质。
  4. 最大公约数：\(\gcd(x,y)\)，在无混淆意义的时侯可以写作 \((x,y)\)。
  5. 最小公倍数：\(\operatorname{lcm}(x,y)\)，在无混淆意义的时侯可以写作 \([x,y]\)。

数论函数常见符号

求和符号：\(\sum\) 符号，表示满足特定条件的数的和。举几个例子：

  • \(\sum_{i=1}^n i\) 表示 \(1+2+\dotsb+n\) 的和。其中 \(i\) 是一个变量，在求和符号的意义下 \(i\) 通常是 正整数或者非负整数（除非特殊说明）。这个式子的含义可以理解为，\(i\) 从 \(1\) 循环到 \(n\)，所有 \(i\) 的和。这个式子用代码的形式很容易表达。当然，学过简单的组合数学的同学都知道 \(\sum_{i=1}^n i=\frac{n(n+1)}{2}\)。
  • \(\sum_{S\subseteq T}|S|\) 表示所有被 \(T\) 包含的集合的大小的和。
  • \(\sum_{p\le n,p\perp n}1\) 表示的是 \(n\) 以内有多少个与 \(n\) 互质的数，即 \(\varphi(n)\)，\(\varphi\) 是欧拉函数。

求积符号：\(\prod\) 符号，表示满足特定条件的数的积。举几个例子：

  • \(\prod_{i=1}^ni\) 表示 \(n\) 的阶乘，即 \(n!\)。在组合数学常见符号中会讲到。
  • \(\prod_{i=1}^na_i\) 表示 \(a_1\times a_2\times a_3\times \dotsb\times a_n\)。
  • \(\prod_{x|d}x\) 表示 \(d\) 的所有因数的乘积。

在行间公式中，求和符号与求积符号的上下条件会放到符号的上面和下面，这一点要注意。

其他常见符号

  1. 阶乘符号 \(!\)，\(n!\) 表示 \(1\times 2\times 3\times \dotsb \times n\)。特别地，\(0!=1\)。
  2. 向下取整符号：\(\lfloor x\rfloor\)，表示小于等于 \(x\) 的最大的整数。常用于分数，比如分数的向下取整 \(\left\lfloor\frac{x}{y}\right\rfloor\)。
  3. 向上取整符号：\(\lceil x\rceil\)，与向下取整符号相对，表示大于等于 \(x\) 的最小的整数。

判定质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

试除法判定质数 (判断 n 是否为质数)

对于一个整数 \(n\)，时间复杂度为 \(O(\sqrt n)\) 

1
2
3
4
5
6
7
8
bool isprime(int n) {
    if (n < 2) return false;

    for (int i = 2; i <= n / i; i++)
        if (n % i == 0)
            return false;
    return true;
}

筛质数 (求 1~n 内有多少个素数)

Eratosthenes 筛法

考虑这样一件事情：如果 \(x\) 是合数，那么 \(x\) 的倍数也一定是合数。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int Eratosthenes(int n) {
    int p = 0;
    for (int i = 0; i <= n; ++i) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;  // prime[p]是i,后置自增运算代表当前素数数量
            if ((long long)i * i <= n)
                for (int j = i * i; j <= n; j += i)
                    // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
                    // 的倍数开始，提高了运行速度
                    is_prime[j] = 0;  // 是i的倍数的均不是素数
        }
    }
    return p;
}

以上为 Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法），时间复杂度是 \(O(n\log\log n)\)。

现在我们就来看看推导过程：

如果每一次对数组的操作花费 \(1\) 个单位时间，则时间复杂度为：

\[ O\left(n\sum_{k=1}^{\pi(n)}{1\over p_k}\right) \]

其中 \(p_k\) 表示第 \(k\) 小的素数。根据 Mertens 第二定理，存在常数 \(B_1\) 使得：

\[ \sum_{k=1}^{\pi(n)}{1\over p_k}=\log\log n+B_1+O\left(1\over\log n\right) \]

所以 Eratosthenes 筛法 的时间复杂度为 \(O(n\log\log n)\)。接下来我们证明 Mertens 第二定理的弱化版本 \(\sum_{k\le\pi(n)}1/p_k=O(\log\log n)\)：

根据 \(\pi(n)=\Theta(n/\log n)\)，可知第 \(n\) 个素数的大小为 \(\Theta(n\log n)\)。于是就有

\[ \begin{aligned} \sum_{k=1}^{\pi(n)}{1\over p_k} &=O\left(\sum_{k=2}^{\pi(n)}{1\over k\log k}\right)\\ &=O\left(\int_2^{\pi(n)}{\mathrm dx\over x\log x}\right)\\ &=O(\log\log\pi(n))=O(\log\log n) \end{aligned} \]

线性筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 \(O(n)\) 了。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
            // i % pri[j] == 0
            // 换言之，i 之前被 pri[j] 筛过了
            // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
            // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
            // 掉就好了
        }
    }
}

上面的这种 线性筛法 也称为 Euler 筛法（欧拉筛法）。

Note

注意到筛法求素数的同时也得到了每个数的最小质因子。

约数

约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

试除法求所有约数

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

最小公倍数

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

1
2
3
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

快速幂

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 求 m^k mod p，时间复杂度 O(logk)。

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

快速幂求逆元

乘法逆元的定义

若整数 \(b\)，\(m\) 互质，并且对于任意的整数 \(a\)，如果满足 \(b\mid a\)，则存在一个整数 \(x\)，使得 \(a/b\equiv a\times x(\bmod m)\)，则称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{−1}(\bmod m)\)。

\(b\) 存在乘法逆元的充要条件是 \(b\) 与模数 \(m\) 互质。当模数 \(m\) 为质数时，\(b^{m−2}\) 即为 \(b\) 的乘法逆元。

1
std::cout << qmi(b, m - 2, m) << '\n';
回到页面顶部