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

素数、筛法与质因数分解

素数与试除法

大于11的整数pp,如果正约数只有11和pp本身,就称pp为素数;否则称为合数。形式化地说:

p>1,d∣p⟹d∈{1,p}p>1,\qquad d\mid p\Longrightarrow d\in\lbrace 1,p\rbrace

11既不是素数,也不是合数,这是判素数时最容易漏掉的边界。

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

非平凡因子:除11和nn本身以外的正因子。

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,可以避免p2p^2在比较以前溢出。单次判定的时间复杂度为O(n)O(\sqrt n),适合询问次数不多、数值范围也不太大的情况。

埃氏筛

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

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

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(nlog⁡log⁡n)O(n\log\log n),空间复杂度为O(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∣ip\mid i时,pp就是ii的最小质因子。对于后面的素数q>pq>p,iqiq仍然含有更小的质因子pp,不应该在当前这一轮标记。

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

质因数分解

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

n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}

其中p1,p2,…,pkp_1,p_2,\ldots,p_k互不相同,αi\alpha_i为正整数。分解单个整数时,可以像判素数一样枚举到n\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>1n>1,剩下的nn一定是一个质数。原因是此时已经不存在不超过当前n\sqrt n的因子,如果它还是合数,就会与试除法的结论矛盾。

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

约数

约数总是成对出现。若d∣nd\mid n,那么n/dn/d也是nn的约数,因此可以在O(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;
}

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

若nn的质因数分解为:

n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}

那么一个约数可以从每个pip_i中选择00到αi\alpha_i个,因此约数个数为:

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

约数和为:

σ(n)=∏i=1k(1+pi+pi2+⋯+piαi)\sigma(n)=\prod_{i=1}^{k}(1+p_i+p_i^2+\cdots+p_i^{\alpha_i})

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

GCD、LCM 与互质

最大公因数

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

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

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)

设a=bq+ra=bq+r。如果dd同时整除a,ba,b,那么dd也整除r=a−bqr=a-bq;反过来,如果dd同时整除b,rb,r,那么dd也整除a=bq+ra=bq+r。两组数的公因数完全相同,最大公因数自然也相同。

不断把(a,b)(a,b)替换成(b,a mod b)(b,a\bmod b),直到第二个数变成00:

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

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

最小公倍数

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

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

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

因此:

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

代码中不要直接写a*b/gcd(a,b)。即使最终答案没有超过i64,中间的a⋅ba\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); }

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

快速幂

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

13=(1101)2=8+4+113=(1101)_2=8+4+1

于是:

a13=a8⋅a4⋅aa^{13}=a^8\cdot a^4\cdot a

从低位到高位枚举bb的二进制位。当前位为11时,把当前底数乘入答案;每处理完一位,就让底数平方,并把bb右移一位。

模数较小时,普通的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;
}

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

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

常见模型与例题

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

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

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

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

给定范围nn和qq次询问,每次输出第kk小的素数。题目中的nn达到10810^8,并且询问很多,不能对每个数单独试除。

欧拉筛已经按照从小到大的顺序把素数加入primes,因此第kk小的素数就是primes[k-1]。筛完以后,每次询问都可以O(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(n),回答询问的时间复杂度为O(q)O(q),总空间复杂度为O(n)O(n)。

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

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

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

从22开始试除,找到的第一个因子一定是较小的质因子。因为nn保证由两个质数相乘得到,所以另一半n/pn/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;
}

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

例题三:AtCoder ABC070 C

题目链接:AtCoder ABC070 C Multiple Clocks

有nn个时钟,第ii个时钟每隔TiT_i秒回到起始位置,求所有时钟第一次同时回到起始位置的时间。

一个时刻能让所有时钟同时归位,当且仅当它是所有TiT_i的公倍数;第一次同时归位的时间就是这些数的最小公倍数。依次把当前答案与新的TiT_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,Ti))O(\log\min(ans,T_i)),总时间复杂度可以写成O(nlog⁡V)O(n\log V),其中VV表示数值上界;空间复杂度为O(1)O(1)。

例题四:Codeforces 230B

题目链接:Codeforces 230B T-primes

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

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

所以判定条件只有两个:

  1. xx是完全平方数;
  2. x\sqrt x是素数。

xx最大达到101210^{12},平方根不超过10610^6,可以先筛出10610^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=106M=10^6。预处理时间复杂度为O(Mlog⁡log⁡M)O(M\log\log M),每次询问只需常数次运算,总空间复杂度为O(M)O(M)。

例题五:AtCoder ABC178 C

题目链接:AtCoder ABC178 C Ubiquity

求长度为nn的数字序列数量,要求序列中至少出现一个00,并且至少出现一个99,答案对109+710^9+7取模。

所有序列共有10n10^n个。不含00的序列有9n9^n个,不含99的序列也有9n9^n个;两类序列的交集既不含00也不含99,共有8n8^n个。根据容斥原理:

ans=10n−2⋅9n+8nans=10^n-2\cdot9^n+8^n

nn最大达到10610^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(log⁡n)O(\log n),空间复杂度为O(1)O(1)。

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

常见问题与复杂度分析

常见问题

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

复杂度分析

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

系列文章

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