Skip to content

初等数论

整除、质数、最大公约数、取模、筛法与快速幂。

Updated View as Markdown

数论是 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 个质数、快速幂取模三个数论编程题。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close