这一篇先把这些最常用的工具整理清楚：从素数与筛法开始，接着介绍质因数分解、约数、GCD 与 LCM以及快速幂。扩展欧几里得、乘法逆元和欧拉定理放在下一篇继续讨论。

素数、筛法与质因数分解

素数与试除法

大于$1$的整数$p$，如果正约数只有$1$和$p$本身，就称$p$为素数；否则称为合数。形式化地说：

$$
p>1,\qquad d\mid p\Longrightarrow d\in\lbrace 1,p\rbrace
$$

$1$既不是素数，也不是合数，这是判素数时最容易漏掉的边界。

判断单个整数$n$是否为素数，最直接的方法是试除。若$n$为合数，可以写成$n=ab$。如果$a,b$都大于$\sqrt n$，就会有$ab>n$，与$n=ab$矛盾。因此$n$只要存在非平凡因子，就一定存在一个不超过$\sqrt n$的因子。

非平凡因子：除$1$和$n$本身以外的正因子。

1
2
3
4
5
bool isPrime(i64 n) {
    if (n < 2) return false;
    for (i64 p = 2; p <= n / p; p++) if (n % p == 0) return false;
    return true;
}

这里使用p<=n/p，而不是p*p<=n，可以避免$p^2$在比较以前溢出。单次判定的时间复杂度为$O(\sqrt n)$，适合询问次数不多、数值范围也不太大的情况。

埃氏筛

如果要一次求出$1$到$n$之间的全部素数，对每个数分别试除会浪费大量重复计算。埃氏筛从小到大枚举整数，遇到一个尚未被标记的数$i$，就说明$i$是素数，再把$i$的倍数全部标记为合数。

标记可以直接从$i^2$开始。因为$2i,3i,\ldots,(i-1)i$都含有比$i$更小的因子，前面已经处理过了。

1
2
3
4
5
6
7
8
vector<bool> sieve(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int i = 2; i <= n / i; i++) if (prime[i])
        for (int j = i * i; j <= n; j += i) prime[j] = false;
    return prime;
}

埃氏筛的时间复杂度为$O(n\log\log n)$，空间复杂度为$O(n)$。它的写法简单，绝大多数普通筛素数问题都可以直接使用。

欧拉筛

埃氏筛中，同一个合数可能被不同的素数重复标记。欧拉筛进一步规定：每个合数只由它的最小质因子筛掉一次。

1
2
3
4
5
6
7
8
9
10
11
vector<int> primes;
vector<bool> vis(n + 1);

for (int i = 2; i <= n; i++) {
    if (!vis[i]) primes.push_back(i);
    for (int p : primes) {
        if (p > n / i) break;
        vis[i * p] = true;
        if (i % p == 0) break;
    }
}

内层的break是整个算法的关键。素数按照从小到大的顺序枚举，当第一次遇到$p\mid i$时，$p$就是$i$的最小质因子。对于后面的素数$q>p$，$iq$仍然含有更小的质因子$p$，不应该在当前这一轮标记。

由于每个合数只会被标记一次，欧拉筛的时间复杂度为严格的$O(n)$，空间复杂度为$O(n)$。如果还需要记录每个数的最小质因子，只需把布尔标记改成minp数组，筛掉$i\cdot p$时令minp[i*p]=p即可。

质因数分解

算术基本定理说明：每个大于$1$的整数都可以唯一地写成若干素数幂的乘积：

$$
n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
$$

其中$p_1,p_2,\ldots,p_k$互不相同，$\alpha_i$为正整数。分解单个整数时，可以像判素数一样枚举到$\sqrt n$，但每找到一个质因子，就要把它连续除尽。

1
2
3
4
5
6
7
8
9
10
vector<pair<i64, int>> factor(i64 n) {
    vector<pair<i64, int>> fac;
    for (i64 p = 2; p <= n / p; p++) if (n % p == 0) {
        int c = 0;
        while (n % p == 0) { n /= p; c++; }
        fac.push_back({p, c});
    }
    if (n > 1) fac.push_back({n, 1});
    return fac;
}

循环结束后，如果$n>1$，剩下的$n$一定是一个质数。原因是此时已经不存在不超过当前$\sqrt n$的因子，如果它还是合数，就会与试除法的结论矛盾。

这份代码的时间复杂度为$O(\sqrt n)$，空间复杂度为$O(\log n)$，其中空间用于保存分解结果。

约数

约数总是成对出现。若$d\mid n$，那么$n/d$也是$n$的约数，因此可以在$O(\sqrt n)$时间内枚举全部约数：

1
2
3
4
5
6
7
8
9
vector<i64> divisors(i64 n) {
    vector<i64> d;
    for (i64 x = 1; x <= n / x; x++) if (n % x == 0) {
        d.push_back(x);
        if (x != n / x) d.push_back(n / x);
    }
    sort(d.begin(), d.end());
    return d;
}

完全平方数的平方根只加入一次，否则会重复。

若$n$的质因数分解为：

$$
n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
$$

那么一个约数可以从每个$p_i$中选择$0$到$\alpha_i$个，因此约数个数为：

$$
d(n)=\prod_{i=1}^{k}(\alpha_i+1)
$$

约数和为：

$$
\sigma(n)=\prod_{i=1}^{k}(1+p_i+p_i^2+\cdots+p_i^{\alpha_i})
$$

这两个式子把“统计约数”转成了“统计每个质因子的指数”，后面的很多数论题都会反复用到。

GCD、LCM 与互质

最大公因数

同时整除$a,b$的正整数称为$a,b$的公因数，其中最大的一个记作$\gcd(a,b)$。若$\gcd(a,b)=1$，就称$a,b$互质。

辗转相除法基于下面的恒等式：

$$
\gcd(a,b)=\gcd(b,a\bmod b)
$$

设$a=bq+r$。如果$d$同时整除$a,b$，那么$d$也整除$r=a-bq$；反过来，如果$d$同时整除$b,r$，那么$d$也整除$a=bq+r$。两组数的公因数完全相同，最大公因数自然也相同。

不断把$(a,b)$替换成$(b,a\bmod b)$，直到第二个数变成$0$：

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

对于非负整数，辗转相除法的时间复杂度为$O(\log\min(a,b))$。C++17也提供了std::gcd，包含在头文件numeric中；使用bits/stdc++.h时无需额外引入。

最小公倍数

同时是$a,b$倍数的正整数称为公倍数，其中最小的一个记作$\operatorname{lcm}(a,b)$。根据质因数分解中指数的对应关系，有：

$$
\gcd(a,b)\operatorname{lcm}(a,b)=ab
$$

证明：设$d=\gcd(a,b)$，则$a=dx,b=dy$且$\gcd(x,y)=1$。由于$x,y$互质，$a,b$的最小公倍数为$dxy$，所以$\gcd(a,b)\operatorname{lcm}(a,b)=d\cdot dxy=(dx)(dy)=ab$。

因此：

$$
\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}
$$

代码中不要直接写a*b/gcd(a,b)。即使最终答案没有超过i64，中间的$a\cdot b$也可能先溢出。应当先除后乘：

1
i64 lcm(i64 a, i64 b) { return a && b ? a / gcd(a, b) * b : 0; }

多个数的最大公因数或最小公倍数可以依次合并：

1
2
i64 g = 0, l = 1;
for (i64 x : a) { g = gcd(g, x); l = lcm(l, x); }

这和求数组的和很相似：每次把前面所有数的答案与当前元素继续计算即可。

快速幂

直接计算$a^b$需要连续乘$b$次，时间复杂度为$O(b)$。但指数可以拆成二进制位，例如：

$$
13=(1101)_2=8+4+1
$$

于是：

$$
a^{13}=a^8\cdot a^4\cdot a
$$

从低位到高位枚举$b$的二进制位。当前位为$1$时，把当前底数乘入答案；每处理完一位，就让底数平方，并把$b$右移一位。

模数较小时，普通的i64乘法通常足够；为了让模板在模数较大时仍然安全，可以使用i128承接中间乘积：

1
2
3
4
5
6
7
8
i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; }
i64 qpow(i64 a, i64 b, i64 mod) {
    i64 ans = 1 % mod;
    a %= mod;
    if (a < 0) a += mod;
    for (; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod);
    return ans;
}

循环次数等于$b$的二进制位数，因此时间复杂度为$O(\log b)$，空间复杂度为$O(1)$。这里的模板要求$mod>0$且$b\ge0$。

快速幂解决的是“如何快速计算幂”，并不代表模意义下可以随意进行除法。涉及逆元、欧拉定理和超大指数时，需要继续判断模数与底数的关系，这部分放在模意义下的数和运算中讨论。

常见模型与例题

下面五道题分别对应筛法、质因数分解、GCD 与 LCM、约数性质和快速幂，基本覆盖这一篇的主要内容。

题目 核心知识点 需要注意的地方
洛谷 P3383 欧拉筛 查询的是第$k$小素数
洛谷 P1075 质因数分解 找到较小质因子后输出另一半
AtCoder ABC070 C 多个数的 LCM 必须先除后乘
Codeforces 230B 约数个数、筛法 平方根的浮点误差
AtCoder ABC178 C 快速幂、容斥 连续减法要处理负数

例题一：洛谷 P3383 线性筛素数

题目链接：洛谷 P3383【模板】线性筛素数

给定范围$n$和$q$次询问，每次输出第$k$小的素数。题目中的$n$达到$10^8$，并且询问很多，不能对每个数单独试除。

欧拉筛已经按照从小到大的顺序把素数加入primes，因此第$k$小的素数就是**primes[k-1]**。筛完以后，每次询问都可以$O(1)$回答。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> primes;
    vector<bool> vis(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) primes.push_back(i);
        for (int p : primes) {
            if (p > n / i) break;
            vis[i * p] = true;
            if (i % p == 0) break;
        }
    }
    while (q--) { int k; cin >> k; cout << primes[k - 1] << '\n'; }
    return 0;
}

筛法的时间复杂度为$O(n)$，回答询问的时间复杂度为$O(q)$，总空间复杂度为$O(n)$。

例题二：洛谷 P1075 质因数分解

题目链接：洛谷 P1075 质因数分解

已知$n$是两个不同质数的乘积，要求输出较大的那个质数。

从$2$开始试除，找到的第一个因子一定是较小的质因子。因为$n$保证由两个质数相乘得到，所以另一半$n/p$就是较大的质因子，可以立即输出。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;
    for (i64 p = 2; p <= n / p; p++) if (n % p == 0) { cout << n / p << '\n'; break; }
    return 0;
}

最坏情况下需要枚举到$\sqrt n$，时间复杂度为$O(\sqrt n)$，空间复杂度为$O(1)$。

例题三：AtCoder ABC070 C

题目链接：AtCoder ABC070 C Multiple Clocks

有$n$个时钟，第$i$个时钟每隔$T_i$秒回到起始位置，求所有时钟第一次同时回到起始位置的时间。

一个时刻能让所有时钟同时归位，当且仅当它是所有$T_i$的公倍数；第一次同时归位的时间就是这些数的最小公倍数。依次把当前答案与新的$T_i$求LCM即可。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 gcd(i64 a, i64 b) { return b ? gcd(b, a % b) : a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    i64 ans = 1;
    while (n--) { i64 x; cin >> x; ans = lcm(ans, x); }
    cout << ans << '\n';
    return 0;
}

每次求GCD需要$O(\log\min(ans,T_i))$，总时间复杂度可以写成$O(n\log V)$，其中$V$表示数值上界；空间复杂度为$O(1)$。

例题四：Codeforces 230B

题目链接：Codeforces 230B T-primes

如果一个正整数恰好有三个不同的正约数，就称它为T-prime。对每个给定的$x$，判断它是否为T-prime。

设$x$恰好有三个约数。除去$1$和$x$以后，只剩下一个约数$p$。约数成对出现，因此$p$只能与自己配对，也就是$x=p^2$；同时$p$必须是素数，否则$p$还有其他因子，$x$的约数就会超过三个。

所以判定条件只有两个：

  1. $x$是完全平方数；
  2. $\sqrt x$是素数。

$x$最大达到$10^{12}$，平方根不超过$10^6$，可以先筛出$10^6$以内的全部素数。使用浮点函数开平方以后，还要用整数乘法向两边校正，避免精度误差。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
const int N = 1e6;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<bool> prime(N + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i <= N / i; i++) if (prime[i])
        for (int j = i * i; j <= N; j += i) prime[j] = false;
    int n;
    cin >> n;
    while (n--) {
        i64 x, r;
        cin >> x;
        r = sqrtl((long double)x);
        while ((r + 1) * (r + 1) <= x) r++;
        while (r * r > x) r--;
        cout << (r * r == x && prime[r] ? "YES\n" : "NO\n");
    }
    return 0;
}

设$M=10^6$。预处理时间复杂度为$O(M\log\log M)$，每次询问只需常数次运算，总空间复杂度为$O(M)$。

例题五：AtCoder ABC178 C

题目链接：AtCoder ABC178 C Ubiquity

求长度为$n$的数字序列数量，要求序列中至少出现一个$0$，并且至少出现一个$9$，答案对$10^9+7$取模。

所有序列共有$10^n$个。不含$0$的序列有$9^n$个，不含$9$的序列也有$9^n$个；两类序列的交集既不含$0$也不含$9$，共有$8^n$个。根据容斥原理：

$$
ans=10^n-2\cdot9^n+8^n
$$

$n$最大达到$10^6$，三个幂都用快速幂计算。连续减法可能得到负数，所以使用subM完成模减法。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
const int MOD = 1e9 + 7;

int addM(int a, int b, int mod = MOD) { return (a += b) >= mod ? a - mod : a; }
int subM(int a, int b, int mod = MOD) { return (a -= b) < 0 ? a + mod : a; }
int mulM(int a, int b, int mod = MOD) { return (i64)a * b % mod; }
int qpow(int a, i64 b, int mod = MOD) {
    int ans = 1;
    for (; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;
    int p9 = qpow(9, n), ans = subM(qpow(10, n), p9);
    ans = addM(subM(ans, p9), qpow(8, n));
    cout << ans << '\n';
    return 0;
}

三次快速幂的时间复杂度均为$O(\log n)$，因此总时间复杂度为$O(\log n)$，空间复杂度为$O(1)$。

如果还想继续练习，统计不同质因子数量可以做Codeforces 26A Almost Prime，结合GCD与质因数分解可以做AtCoder ABC142 D Disjoint Set of Common Divisors。

常见问题与复杂度分析

常见问题

  • 为什么$1$不是素数？ 素数必须恰好有两个不同的正约数，而$1$只有一个正约数。把$1$排除以后，算术基本定理中的质因数分解才能保持唯一。
  • 什么时候使用试除，什么时候使用筛法？ 只判断少量整数时使用$O(\sqrt n)$试除；需要处理一个连续范围或大量询问时，先筛出素数通常更合适。
  • 埃氏筛为什么从$i^2$开始？ 更小的倍数$2i,3i,\ldots,(i-1)i$已经被比$i$更小的因子标记过。
  • 欧拉筛为什么在$i\bmod p=0$时停止？ 此时$p$是$i$的最小质因子，继续枚举更大的素数会让合数被重复标记。
  • 质因数分解结束后，为什么还要判断$n>1$？ 试除后剩余的$n$可能是一个大于原平方根的质因子，它不会在循环中被加入答案。
  • LCM为什么要先除后乘？ 两种顺序在数学上相同，但先乘可能产生中间溢出；**a/gcd(a,b)*b**更加安全。
  • 快速幂已经是$O(\log b)$，为什么乘法仍然可能出错？ 快速幂减少的是乘法次数，不会自动扩大整数类型的取值范围。乘积可能超过i64时，仍然要使用i128或快速乘。

复杂度分析

操作 时间复杂度 空间复杂度
单次试除判素数 $O(\sqrt n)$ $O(1)$
埃氏筛 $O(n\log\log n)$ $O(n)$
欧拉筛 $O(n)$ $O(n)$
单个整数质因数分解 $O(\sqrt n)$ $O(\log n)$
枚举全部约数并排序 $O(\sqrt n+d(n)\log d(n))$ $O(d(n))$
辗转相除法 $O(\log\min(a,b))$ $O(\log\min(a,b))$
迭代快速幂 $O(\log b)$ $O(1)$

系列文章

  1. 基础数论入门
  2. 模意义下的数和运算