
数论是 CSP-J 复赛和 GESP 五级的常客。它有个特点:题目往往只有一两行,但里面藏着一个整除性质或者一个取模技巧,想通了代码很短,想不通就只能暴力。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| GESP C++ 五级 | 考点 1:初等数论(素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性);考点 4:辗转相除法、埃氏筛法与线性筛法、唯一分解定理 | 全章 |
| NOI 入门级 | 1.5.3 初等数论 | 全章 |
| CSP-J/S 入门级 | 5.3 初等数论 | 全章 |
整除、因数与倍数
若整数 a 除以整数 b(b \neq 0)的余数为 0,就说 b 整除 a,记作 b \mid a。此时 b 是 a 的因数(约数),a 是 b 的倍数。
几条常用性质:
- 若
a \mid b且b \mid c,则a \mid c。 - 若
a \mid b且a \mid c,则a \mid (bx + cy),其中x、y是任意整数。 - 若
a \mid b且b \mid a,则a = b或a = -b。
质数与合数
只有 1 和它本身两个正因数的正整数叫质数(素数),否则叫合数。
两个容易考的点:
- 1 既不是质数也不是合数。 它只有一个正因数。
- 2 是最小的质数,也是唯一的偶质数。 其它偶数都能被 2 整除,都是合数。
判断单个数是不是质数,试除到 \sqrt n 就够了。如果 n 有大于 \sqrt n 的因数,那必然有一个小于 \sqrt n 的对应因数,早就被发现了。
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) { // 写成 i * i <= n 避免浮点误差
if (n % i == 0) return false;
}
return true;
}试除法判断单个数是 O(\sqrt n)。n 到 10^{12} 时大约是 10^6 次运算,完全够用。但要用它判断 1 到 n 的每一个数,总复杂度是 O(n\sqrt n),n = 10^6 就超时了,这时要换成筛法。
质因数分解与唯一分解定理
唯一分解定理(算术基本定理):任何一个大于 1 的整数,都能唯一地分解成若干质数的乘积。
n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}
分解的方法是从小到大试除,除得动就一直除,直到商为 1。
// n 最大可达 10^12,超过 int 范围,参数要用 long long
void factorize(long long n) {
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
cout << i << "^" << cnt << endl; // 质因数 i 出现了 cnt 次
}
}
if (n > 1) cout << n << "^1" << endl; // 剩下的就是最后一个质因数
}复杂度是 O(\sqrt n)。最后那个 if (n > 1) 不能漏:如果原数本身是质数,或者分解到最后剩一个大于 \sqrt n 的质因数,循环里抓不到它。
最大公约数与最小公倍数
a 和 b 的最大公约数记作 \gcd(a, b),最小公倍数记作 \operatorname{lcm}(a, b)。
辗转相除法(欧几里得算法)利用一个性质:\gcd(a, b) = \gcd(b, a \bmod b)。反复用这个式子把两个数变小,直到其中一个变成 0,另一个就是答案。
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}最小公倍数由最大公约数算出:
\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}
写成代码时要注意溢出。a、b 都接近 10^9 时,a \times b 会到 10^{18} 量级,直接写 a * b / gcd(a, b) 可能先溢出再除。先除以 gcd 再乘:
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}这两个函数在《递归算法》里作为递归的例子也出现过,那里有更详细的推导。
取整与取模
C++ 的整数除法向零取整,7 / 2 是 3,-7 / 2 是 -3,不是 -4。需要向下取整时用 floor(),或者自己处理负数。
取模的结果符号跟着被除数走:
cout << 7 % 3 << endl; // 1
cout << -7 % 3 << endl; // -1,不是 2需要非负余数时,加上模数再取一次:
int mod = ((x % m) + m) % m;同余的记号是 a \equiv b \pmod m,表示 a 和 b 除以 m 的余数相同。同余式可以相加、相减、相乘,但不能随便相除,这一条留到《数论进阶》再展开。
奇偶性
判断奇偶只看最低位:x & 1 为 1 就是奇数,为 0 就是偶数。比 x % 2 稍快,也更直接。
奇偶性的常见用处:
- 两个奇数的和是偶数,一奇一偶的和是奇数。
- 连续整数的乘积一定是偶数。
- 总和为奇数时,不可能把它平均分成若干对。
素数筛法
要预处理出 1 到 n 内所有质数,用筛法。
埃氏筛
从 2 开始,把每个质数的倍数标记成合数。
const int MAXN = 10000005;
bool isPrime[MAXN];
vector<int> primes;
void sieve(int n) {
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) { // 从 i*i 开始
isPrime[j] = false;
}
}
}
}从 i^2 开始标记是关键优化,因为 2i、3i 这些更小的倍数已经被更小的质数标记过了。复杂度 O(n \log \log n),接近线性,n = 10^7 也能跑。
线性筛
线性筛保证每个合数只被它的最小质因数筛掉一次,复杂度是严格的 O(n)。
const int MAXN = 10000005;
bool isPrime[MAXN];
vector<int> primes;
void linearSieve(int n) {
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.push_back(i);
for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0) break; // 保证每个合数只被筛一次
}
}
}if (i % primes[j] == 0) break; 这一行是核心。它保证 i \times p_j 的最小质因数就是 p_j,所以每个合数只会在它最小质因数那一轮被标记。
需要质数表的时候,线性筛顺手就得到了,所以在数论题里更常用。
快速幂
计算 a^b \bmod m。直接循环乘 b 次,b = 10^9 时不可能跑完。快速幂把指数拆成二进制,每次把底数平方、指数减半,只需要 O(\log b) 次乘法。
long long fastPow(long long a, long long b, long long mod) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod; // 这一位是 1,乘进去
a = a * a % mod; // 底数平方
b >>= 1; // 指数右移一位
}
return res;
}不用取模时把 mod 设成一个足够大的数即可。这个算法也叫「倍增」,本质和《倍增法》里的思路一样。
复杂度速查
| 操作 | 复杂度 | 适用规模 |
|---|---|---|
| 试除判断单个数 | O(\sqrt n) |
n \le 10^{12} |
| 质因数分解 | O(\sqrt n) |
n \le 10^{12} |
| 辗转相除求 gcd | O(\log n) |
任意 |
| 埃氏筛 | O(n \log \log n) |
n \le 10^7 |
| 线性筛 | O(n) |
n \le 10^7 |
| 快速幂 | O(\log b) |
任意 |
初赛选择题精选
数论是 GESP 五级笔试的必考内容。下面 8 道题按考点分类编写,覆盖质数识别、约数个数、最大公约数、负数取模、快速幂、筛法复杂度、奇偶性与唯一分解定理这些高频考点。先自己做,再看答案与解析。
题 1(质数识别)
下列四个数中,是质数的是( )。
A. 91 B. 87 C. 89 D. 93
答案:C
解析:91 = 7 \times 13,87 = 3 \times 29,93 = 3 \times 31,都能被更小的质数整除;只有 89 除不动 2、3、5、7(\sqrt{89} < 10),是质数。三个非质数都是「邻近 90 的合数」,这是选择题最爱的出题区间。
题 2(约数个数)
36 的正约数一共有多少个?
A. 6 B. 8 C. 9 D. 12
答案:C
解析:由唯一分解定理 36 = 2^2 \times 3^2,约数个数等于每个质因数的指数加 1 再相乘:(2+1) \times (2+1) = 9 个。列出验证:1、2、3、4、6、9、12、18、36,正好 9 个。这条「指数加 1 相乘」的公式是数论笔试的常客。
题 3(最大公约数与最小公倍数)
两个正整数的最大公约数是 4,最小公倍数是 48,其中一个数是 16,另一个数是多少?
A. 8 B. 12 C. 24 D. 32
答案:B
解析:正整数有一条性质:两数之积 = 最大公约数 × 最小公倍数。所以另一个数是 \frac{4 \times 48}{16} = 12。验证:\gcd(16, 12) = 4,\operatorname{lcm}(16, 12) = 48,正确。
题 4(负数取模)
在 C++ 中,表达式 -7 % 3 的值是( )。
A. -1 B. 1 C. -2 D. 2
答案:A
解析:C++ 的取模符号跟着被除数走,-7 = 3 \times (-3) - 1,余数是 -1。需要非负余数时,写成 ((x % m) + m) % m,这是用取模实现循环下标时的必备写法。
题 5(快速幂的运算量)
用快速幂计算 a^b \bmod p,其中 b = 10^9。大约需要进行多少次乘法运算?
A. 约 10^9 次 B. 约 10^6 次 C. 约 60 次 D. 约 30 次
答案:C
解析:快速幂每轮把指数减半,10^9 < 2^{30},所以递归(循环)只有约 30 层;每层一次平方,指数位为 1 时还要多乘一次底数,最多再加 30 次,总共约 60 次乘法。这正是快速幂把 O(b) 降到 O(\log b) 的含义。
题 6(筛法复杂度)
用埃氏筛法求出 10^7 以内的所有质数,时间复杂度约为( )。
A. O(n) B. O(n \log n) C. O(n \log \log n) D. O(n^2)
答案:C
解析:埃氏筛的总运算量是 \sum_{p \le n} \frac{n}{p}(对每个质数 p 划掉它的倍数),而这个和约为 n \ln \ln n,即 O(n \log \log n)。
和线性筛的区别:线性筛(欧拉筛)是严格的 O(n),每个合数只被它的最小质因数筛一次。n = 10^7 时两者都能过,但线性筛常数更大,实际差距没有理论那么大。
题 7(奇偶性判断)
下列说法正确的是( )。
A. 两个奇数的和一定是奇数 B. 奇数个奇数相加的结果一定是奇数 C. 两个奇数的积一定是偶数 D. 偶数除以 2 一定是偶数
答案:B
解析:逐项分析:
- A 错:奇 + 奇 = 偶(如
3 + 5 = 8)。 - B 对:奇数个奇数相加,结果一定是奇数(如
1+3+5 = 9)。奇数个这个条件是关键。 - C 错:奇 × 奇 = 奇(如
3 \times 5 = 15)。 - D 错:如
6 \div 2 = 3,是奇数。
记忆口诀:奇偶性只看得数里的「奇数个数」——加法时奇数个数为奇数则和为奇数,乘法时只要有一个偶数结果就是偶数。
题 8(唯一分解定理)
360 的正因数共有多少个?
A. 12 B. 20 C. 24 D. 36
答案:C
解析:先分解:360 = 2^3 \times 3^2 \times 5^1。由唯一分解定理,正因数个数等于各指数加 1 的乘积:
(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24
为什么是「指数 +1」相乘? 因为因数 2^a 3^b 5^c 中,a 可以取 0 \sim 3 共 4 种,b 取 0 \sim 2 共 3 种,c 取 0 \sim 1 共 2 种,组合起来就是 4 \times 3 \times 2。这是数论选择题的高频考点。
练习
练习 1:质因数分解
题目描述
输入一个大于 1 的整数 n,按从小到大的顺序输出它的质因数分解式,格式为 n=p1^e1*p2^e2*...(每个质因数都要带指数,包括指数为 1 的)。
输入格式
一个整数 n。
输出格式
输出一行,表示质因数分解式。
数据范围
2 \le n \le 10^{12}。
输入输出样例
输入
180输出
180=2^2*3^2*5^1输入
7输出
7=7^1题目分析
正文质因数分解模板的直接落地,三个要点:一是 n 用 long long(10^{12} 超出 int);二是试除到 \sqrt n;三是循环结束后如果 n > 1,剩下的一定是最后一个质因数(它可能就是 n 本身,比如输入质数 7 时输出 7=7^1)。
参考代码
练习 2:第 n 个质数
题目描述
质数从小到大依次是 2、3、5、7、11……求第 n 个质数。
输入格式
一个整数 n。
输出格式
输出一个整数,表示第 n 个质数。
数据范围
1 \le n \le 100000。
输入输出样例
输入
100000输出
1299709题目分析
批量找质数用筛法。筛到多大才够?由质数定理,第 10^5 个质数大约是 n \ln n \approx 10^5 \times 11.5 \approx 1.15 \times 10^6,筛到 1.3 \times 10^6 留足余量。
实现时把筛法和计数合在一个循环里:每发现一个新质数就计数加 1,数够 n 个就可以停了。注意内层标记循环里 i \times i 用 long long 防止溢出。
参考代码
埃氏筛的复杂度是 O(M \log \log M),M = 1.3 \times 10^6 时几十毫秒就能跑完,换成线性筛更快,但在这个规模下没有必要。
练习 3:快速幂
题目描述
给定 a、b、p,计算 a^b \bmod p 并输出。特别地,b = 0 时输出 1 % p。
输入格式
一行三个整数 a、b、p。
输出格式
输出一个整数,表示 a^b \bmod p 的结果。
数据范围
0 \le a, b < 2^{31},2 \le p \le 10^9。
输入输出样例
输入
2 10 1000输出
24说明:2^{10} = 1024,对 1000 取模得 24。
题目分析
正文快速幂模板的直接落地。三个易错点再强调一遍:res 初始化为 1 % p(p = 1 时任何数模 1 都是 0);底数要先对 p 取模;每步乘完都要取模,不能最后再取。
参考代码
2^{10} = 1024 的验证:二进制 10 = 1010_2,共进行 4 次平方、2 次额外乘法,总共 6 次乘法,而不是暴力乘的 10 次。
常见易错点
- 忘记处理 1:它既不是质数也不是合数。
- 质因数分解最后剩下的
n > 1漏掉,质数会被分解成「什么都没有」。 lcm直接写a * b / gcd会溢出,要先除后乘。- 取模结果为负时忘记修正,用来做数组下标会崩。
- 线性筛的
break条件写成其它形式,复杂度会退化,甚至筛错。 - 快速幂里底数要先取模,指数很大时也要注意类型。
小结
- 质数判断用试除到
\sqrt n,批量求质数用筛法。 - 唯一分解定理是数论的基石,分解方法是从小到大试除。
- 辗转相除法求最大公约数,
\operatorname{lcm}(a, b) = a / \gcd(a, b) \times b。 - 辗转相除、埃氏筛、线性筛、快速幂是数论题的四大工具,都能背下来直接用。
- 会用「指数加 1 相乘」计算正整数的约数个数,会用「两数之积 = gcd × lcm」互算。
- 会写质因数分解、筛法找第 n 个质数、快速幂取模三个数论编程题。