NOI C++ 课程体系 / 数学基础篇 / 第3讲
CSP-J 入门级 · 初等数论 · m6-03

整除、质数
与模运算

从古希腊的素数之谜到现代密码学的基石——掌握数论三大核心工具，让程序拥有"数学直觉"！

6 大模块 3 大核心概念 2 种筛法 5 大易错点 12 道分层练习
本讲 · 第 53/56 讲初等数论一：整除、质数、模运算
模块 01

情景导航

用故事建立直觉，用类比理解抽象概念。

故事埃拉托斯特尼与"筛子"

公元前3世纪，古希腊学者埃拉托斯特尼（Eratosthenes）想找出所有小于100的质数。

他没有逐个试除，而是发明了一个绝妙的方法：

写下2~100，划掉2的倍数，再划掉3的倍数，再划掉5的倍数...
剩下的就是质数！

这个方法被称为"埃氏筛法"（Sieve of Eratosthenes），至今仍是计算机求质数的首选算法之一。

两千多年后的今天，我们在编程竞赛中依然在用这个古老而优雅的思想。

💡 为什么数论是竞赛必考？

数论题目看似简单（都是整数运算），但往往隐藏着深刻的数学规律。不懂数论，暴力超时；懂了数论，O(1)秒杀。

GCD、质因数分解、模运算——这三个工具贯穿了整个信息学竞赛的数学部分。

①生活类比：数论无处不在
🎵

音乐节拍 = GCD

两种节奏要同步，需要找最小公倍数。

→ LCM = a×b / GCD
🔐

密码锁 = 模运算

密码转了一圈又回到起点，本质是 mod。

→ 循环 = 取模
🧱

铺砖 = 因数

房间长宽都能被砖的尺寸整除，才能铺满。

→ 整除的实际意义
🔑

RSA加密 = 质数

两个大质数相乘容易，分解却极难。

→ 现代网络安全基石
②编程定义：本讲知识地图

本讲涵盖大纲中 "初等数论" 的前半部分核心知识点。

📌 本讲核心知识地图

板块核心内容对应大纲
整除因数、倍数、整除判定整除、因数、倍数
质数质数判定、合数、指数质（素）数、合数、指数
模运算取余、同余、负数取模模运算与取余
唯一分解算术基本定理、质因数分解整数唯一分解定理
GCD辗转相除法、LCM辗转相除法（欧几里得算法）
筛法埃氏筛法、线性筛法素数筛法
③核心口诀
🔑 口诀一：辗转相除求GCD

大数除以小数，余数替换大数
余数为零停手，小数就是GCD

🔑 口诀二：唯一分解定理

任何大于1的整数，都能唯一写成
若干个质数的幂次之积

🔑 口诀三：模运算分配律

加、减、乘可分配，除法要小心
(a+b)%m = (a%m + b%m) % m

模块 02

知识探究

系统掌握整除、质数、模运算、唯一分解、GCD与筛法六大核心板块。

1整除、因数与倍数 基础

整除：若整数 a ÷ b 的余数为 0，则称 b 整除 a，记作 b | a。

概念定义示例C++判定
因数(约数)若 b|a，则b是a的因数1,2,3,6 都是 6 的因数a % b == 0
倍数若 b|a，则a是b的倍数6,12,18 都是 6 的倍数a % b == 0
真因数除了自身以外的因数6的真因数：1,2,3b != a && a%b==0

🔍 高效枚举因数：只需枚举到 √n

C++O(√n) 枚举所有因数
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        cout << i << " ";       // i 是因数
        if (i != n / i)
            cout << n/i << " ";  // n/i 也是因数（避免重复）
    }
}
💡 关键优化：因数成对出现！若 i 是 n 的因数，则 n/i 也是。所以只需遍历到 √n，时间复杂度从 O(n) 降到 O(√n)。
2质数与合数 必考
类别定义示例注意
质数(素数)大于1，只有1和自身两个因数2,3,5,7,11,13...2是最小的质数，也是唯一的偶质数
合数大于1，有超过两个因数4,6,8,9,10,12...最小的合数是4
1既不是质数也不是合数1⚠️ 特殊！很多题目在这里设坑

🔍 质数判定 O(√n)：

C++判断一个数是否为质数
bool isPrime(int n) {
    if (n < 2) return false;       // 1和负数不是质数
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false; // 找到因数，不是质数
    }
    return true;
}
🔑 质数相关重要结论

① 2 是唯一偶质数 → 判质数先特判2
② 质数有无穷多个（欧几里得证明）
③ 100以内质数共 25 个（建议背诵前几个）
④ 任意大于1的整数至少有一个质因数

3模运算与取余 高频陷阱

模运算：a mod m = a 除以 m 的余数，C++中写作 a % m。

性质公式说明
加法(a+b)%m = (a%m + b%m) % m✅ 可分配
减法(a-b)%m = (a%m - b%m + m) % m✅ 可分配，+m防负
乘法(a*b)%m = (a%m * b%m) % m✅ 可分配
除法(a/b)%m ≠ (a%m)/(b%m)❌ 不可直接分配！
⚠️

负数取模的致命陷阱

❌ C++行为
-7 % 3 = -1（不是2！）
余数符号 = 被除数符号
✅ 安全写法
((a % m) + m) % m
保证结果 ∈ [0, m-1]
🔑 模运算核心原则

① 随时取模：防止中间结果溢出
② 减法补m：(a-b+m)%m 防负数
③ 除法用逆元：模意义下除法需乘法逆元（进阶内容）
④ 负数处理：((a%m)+m)%m 万能公式

4整数唯一分解定理 核心

📜 算术基本定理（Fundamental Theorem of Arithmetic）

任何大于1的正整数 n，都可以唯一地表示为若干个质数的幂次之积：

n = p₁^α₁ × p₂^α₂ × ... × pₖ^αₖ

其中 p₁ < p₂ < ... < pₖ 是质数，αᵢ ≥ 1 是正整数。这种表示是唯一的。

🖐 示例：

1
360 的质因数分解
360 = 2³ × 3² × 5¹
2
因数个数公式
d(n) = (α₁+1)(α₂+1)...(αₖ+1)
d(360) = (3+1)(2+1)(1+1) = 4×3×2 = 24
3
因数和公式
σ(n) = (p₁⁰+p₁¹+...+p₁^α₁) × ... × (pₖ⁰+...+pₖ^αₖ)
σ(360) = (1+2+4+8)(1+3+9)(1+5) = 15×13×6 = 1170
C++质因数分解 O(√n)
void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << "^" << cnt << " ";
        }
    }
    if (n > 1) cout << n << "^1"; // 剩余的大质因子
}
5辗转相除法（GCD） 必考

最大公约数(GCD)：能同时整除a和b的最大正整数。
最小公倍数(LCM)：能同时被a和b整除的最小正整数。

GCD(a,b) × LCM(a,b) = a × b
LCM(a,b) = a / GCD(a,b) × b  ← 先除后乘防溢出！

🖐 手推：GCD(48, 18)

1
48 ÷ 18 = 2 ... 余 12
GCD(48,18) = GCD(18,12)
2
18 ÷ 12 = 1 ... 余 6
GCD(18,12) = GCD(12,6)
3
12 ÷ 6 = 2 ... 余 0
余数为0，GCD = 6
C++递归 & 内置函数
// 方法1：手写递归
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 方法2：C++17 内置（推荐）
#include <numeric>
int g = std::gcd(a, b);
int l = std::lcm(a, b);
🔑 GCD/LCM 注意事项

① GCD(a,0) = a，GCD(a,a) = a
② 计算LCM时先除后乘：a/gcd(a,b)*b，防止 a*b 溢出
③ 辗转相除法时间复杂度：O(log min(a,b))，极快
④ 多个数的GCD：gcd(a,b,c) = gcd(gcd(a,b), c)

6素数筛法 高效

当需要求出 [2, N] 范围内所有质数时，逐个判定太慢。筛法可以批量筛选！

🔹 埃氏筛法 O(N log log N)
  • 从2开始，将每个质数的倍数标记为合数
  • 未被标记的就是质数
  • 简单好写，N≤10⁷够用
  • 缺点：合数可能被多次标记
🔸 线性筛(欧拉筛) O(N)
  • 每个合数只被其最小质因子筛掉一次
  • 严格 O(N)，N≤10⁸可用
  • 代码稍复杂，但效率最优
  • 竞赛推荐掌握
C++埃氏筛法
const int MAXN = 1000000;
bool is_composite[MAXN];
vector<int> primes;

void eratosthenes() {
    for (int i = 2; i < MAXN; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            for (int j = i * i; j < MAXN; j += i)
                is_composite[j] = true;
        }
    }
}
C++线性筛（欧拉筛）
void linear_sieve() {
    for (int i = 2; i < MAXN; i++) {
        if (!is_composite[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] < MAXN; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // 核心：保证最小质因子筛
        }
    }
}
💡 线性筛的核心：if (i % primes[j] == 0) break; 确保每个合数只被其最小质因子筛掉一次，从而保证 O(N)。
模块 03

实践应用

通过详细的手推追踪，巩固GCD、唯一分解和模运算。

题1GCD手推追踪

题目：用辗转相除法求 GCD(1071, 462)，并求 LCM(1071, 462)。

查看参考答案
1
1071 ÷ 462 = 2 ... 余 147
GCD(1071,462) → GCD(462,147)
2
462 ÷ 147 = 3 ... 余 21
GCD(462,147) → GCD(147,21)
3
147 ÷ 21 = 7 ... 余 0
余数为0 → GCD = 21

LCM计算（先除后乘防溢出）：

LCM = 1071 / 21 × 462 = 51 × 462 = 23562

验证：21 × 23562 = 494802 = 1071 × 462 ✅

题2唯一分解实战

题目：求 720 的所有因数个数和因数之和。

查看参考答案

第一步：质因数分解

720 = 72 × 10 = 8×9 × 2×5 = 2³ × 3² × 2¹ × 5¹ = 2⁴ × 3² × 5¹

第二步：因数个数

d(720) = (4+1)(2+1)(1+1) = 5 × 3 × 2 = 30

第三步：因数之和

σ(720) = (1+2+4+8+16)(1+3+9)(1+5)

= 31 × 13 × 6 = 2418

题3同余方程入门

题目：求满足 3x ≡ 1 (mod 7) 的最小正整数 x。

查看参考答案

含义：3x mod 7 = 1，即 3x 除以 7 余 1。

方法：枚举法（小模数适用）

x3x3x mod 7结果
133✗
266✗
392✗
4125✗
5151✓

答案：x = 5

注：这就是3在模7下的乘法逆元，进阶可用扩展欧几里得求解。

模块 04

总结提升

1核心要点总结
知识板块必须记住的核心
整除/因数a%b==0 判定；枚举因数 O(√n)；因数成对出现
质数2是最小且唯一偶质数；1非质非合；判定 O(√n)
模运算加减乘可分配；减法+m防负；除法不可直接分配
唯一分解n=p₁^α₁×...×pₖ^αₖ；因数个数=(α₁+1)...(αₖ+1)
GCD/LCM辗转相除 O(log n)；LCM=a/gcd*b（先除后乘）
埃氏筛O(N log log N)；标记质数的倍数
线性筛O(N)；每个合数被最小质因子筛一次；i%p[j]==0时break
2拓展：质数与RSA加密

💡 为什么质数如此重要？

现代互联网安全的基础——RSA加密算法，完全依赖于质数的一个特性：

两个大质数相乘很容易，但把乘积分解回两个质数极其困难。

例如：选择两个200位的质数 p, q，计算 n = p×q 只需毫秒级；但给定 n，分解出 p 和 q，即使用超级计算机也需要数万年。

这就是"单向函数"的思想——正向容易，逆向极难。你的网银、微信、HTTPS 都靠它保护！

3思考与启发

💡 学完本讲，你应该掌握的6项能力

1. 能用 a % b == 0 判定整除，O(√n) 枚举因数。

2. 能正确判定质数，牢记 1非质非合、2是唯一偶质数。

3. 掌握模运算分配律，会用 ((a%m)+m)%m 处理负数。

4. 能对整数做质因数分解，并用公式算因数个数/和。

5. 能用辗转相除法求GCD，先除后乘求LCM防溢出。

6. 能写出埃氏筛和线性筛，理解两者区别。

模块 05

学习检测

5 个初赛高频易错点，每个都有口诀帮你记住。

易错1

认为1是质数

❌ 错误
"1是质数"
"1只有一个因数，所以是质数"
✅ 正确
1 既不是质数也不是合数
质数定义要求"恰好两个因数"
口诀：1非质也非合，质数从2才开始！
易错2

LCM计算溢出

❌ 错误
lcm = a * b / gcd(a,b);
a*b 可能先溢出！
✅ 正确
lcm = a / gcd(a,b) * b;
先除后乘，保证不溢出
口诀：LCM先除再乘，顺序反了会爆掉！
易错3

模运算减法出负数

❌ 错误
(3 - 5) % 7 = -2
期望得到正余数5
✅ 正确
((3-5) % 7 + 7) % 7 = 5
万能公式：((a%m)+m)%m
口诀：模减可能负，加m再取模保平安！
易错4

质因数分解漏掉大质因子

❌ 错误
分解14：循环到√14≈3
只找到2，漏掉了7
✅ 正确
循环结束后检查：
if (n > 1) → n本身是大质因子
14 = 2¹ × 7¹ ✅
口诀：分解完别忘检查，剩大于1就是质因子！
易错5

线性筛忘记break条件

❌ 错误
省略 if(i%p[j]==0) break;
合数被多次标记 → 退化为 O(N log N)
✅ 正确
if (i % primes[j] == 0) break;
保证每个合数只被最小质因子筛一次
口诀：线性筛灵魂在break，少了就不是O(N)！
速查初等数论速查表
知识点关键数据/结论
质数判定试除法 O(√n)；1非质非合；2是唯一偶质数
因数枚举只需遍历到 √n；因数成对出现
GCD辗转相除 O(log n)；gcd(a,0)=a
LCMa/gcd(a,b)*b（先除后乘）
唯一分解n = ∏pᵢ^αᵢ；因数个数 = ∏(αᵢ+1)
模运算(a±b)%m, (a*b)%m 可分配；除法不行
负数取模((a%m)+m)%m
埃氏筛O(N log log N)；标记倍数
线性筛O(N)；i%p[j]==0时break
100以内质数25个：2,3,5,7,11,13,17,19,23,29...
📌知识点笔记卡

🔢 整除与因数

a%b==0 → b|a

枚举到√n，成对出现

1是所有正整数的因数

⭐ 质数

2是最小且唯一偶质数

1非质非合

判定O(√n)，筛法批量求

🔄 模运算

加减乘可分配

减法+m防负

((a%m)+m)%m 万能

🧩 唯一分解

n = ∏pᵢ^αᵢ

因数个数 = ∏(αᵢ+1)

分解后别忘了检查n>1

📐 GCD/LCM

辗转相除 O(log n)

LCM = a/gcd*b

先除后乘防溢出

🔍 筛法

埃氏筛 O(NloglogN)

线性筛 O(N)

i%p[j]==0 → break

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增，点击展开答案与解析。

🟢 A组 · 基础（4题）

A1选择题

下列哪个数是质数？（）

A. 1   B. 2   C. 9   D. 15

查看参考答案

答案：B. 2

1非质非合；9=3²是合数；15=3×5是合数；2是最小的质数。

考点：质数定义为「大于 1 且只有 1 和自身两个正因数」的自然数，由此可知 2 是最小的质数，也是唯一的偶质数。

易错：把 1 当作质数，或认为 2 是偶数所以属于合数。

A2选择题

GCD(12, 18) = （）

A. 3   B. 6   C. 12   D. 36

查看参考答案

答案：B. 6

12=2²×3, 18=2×3², GCD=2×3=6。或辗转相除：18%12=6, 12%6=0 → GCD=6。

考点：最大公约数有两条路：分解质因数后取公共质因子的「最小指数幂」之积；或用辗转相除 gcd(a,b)=gcd(b,a%b) 递推。

易错：把 GCD 理解成公因数的个数，或把两数的因数简单相加。

A3选择题

在C++中，-10 % 3 的值是（）

A. 2   B. -1   C. 1   D. -2

查看参考答案

答案：B. -1

C++中余数符号同被除数：-10 = (-3)×3 + (-1)，余数为-1。

考点：C++ 中 % 的结果符号与被除数一致：把 -10 写成「商 × 除数 + 余数」时，商向零截断，余数自然为负。

易错：按数学上的模定义算成 2，误以为余数在任何情况下都非负。

A4选择题

36的因数共有（）个

A. 6   B. 8   C. 9   D. 12

查看参考答案

答案：C. 9

36 = 2² × 3²，因数个数 = (2+1)(2+1) = 9。
列举：1,2,3,4,6,9,12,18,36。

考点：因数个数公式：把 n 分解为 paqb… 后，因数个数等于 (a+1)(b+1)…。

易错：只数到 √36 = 6 就收手，漏掉与之配对的大因数 9、12、18、36。

🟡 B组 · 提高（4题）

B1选择题

LCM(12, 18) = （）

A. 6   B. 36   C. 72   D. 216

查看参考答案

答案：B. 36

LCM = 12/GCD(12,18) × 18 = 12/6 × 18 = 2×18 = 36。

考点：最小公倍数常用公式 LCM(a,b) = a / GCD(a,b) * b，先除后乘还能避免大数相乘溢出（在编程中尤其重要）。

易错：直接把 a × b = 216 当成 LCM，忘记还要除以两数的最大公约数。

B2填空题

将 120 质因数分解：120 = 2^___ × 3^___ × 5^___

查看参考答案
C++完整参考代码
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                                  // 例如 120
    cout << n << " = ";

    bool first = true;                         // 控制 1 只出现在中间
    for (int p = 2; p * p <= n; p++) {         // 只需试到 sqrt(n)
        if (n % p != 0) continue;              // p 不是因子就跳过

        int e = 0;
        while (n % p == 0) {                   // 反复除，统计指数
            n /= p;
            e++;
        }
        if (!first) cout << " * ";
        cout << p << "^" << e;
        first = false;
    }

    if (n > 1) {                               // 剩下的大于 sqrt 的质因子
        if (!first) cout << " * ";
        cout << n << "^1";
    }
    cout << endl;                              // 120 = 2^3 * 3^1 * 5^1
    return 0;
}

答案：120 = 23 × 31 × 51（也就是 23 × 3 × 5 = 8 × 15 = 120）。

思路：从最小的质数 2 开始逐个试。只要 p 能整除 n，就一直除下去，除了几次，指数就是几——120 除以 2 得 60、30、15，除不动时已经除了 3 次，于是 2 的指数是 3；接着试 3：15÷3 = 5，指数 1；再试 4（不整除）、5：5÷5 = 1，指数 1。循环条件 p * p <= n 让试除只做到 √n，效率高很多。

考点：试除法质因数分解、while (n % p == 0) 统计指数、整除与质数的基本性质。

易错：① 循环条件写成 p <= n 会又慢又可能死循环，应写 p * p <= n；② 最容易漏的是"除完以后剩下的 n 如果还大于 1，它本身就是最后一个质因子"——比如 14 = 2 × 7，试到 2 之后 n 变成 7，7×7 > 7 跳出循环，必须补输 7^1；③ 指数为 1 时也要写出"^1"，不要省略。

B3选择题

表达式 ((5 - 8) % 7 + 7) % 7 的值是（）

A. -3   B. 4   C. 3   D. 0

查看参考答案

答案：B. 4

(5-8)%7 = -3%7 = -3；(-3+7)%7 = 4%7 = 4。

考点：这是负数取模的规范写法：先让 C++ 得到可能为负的余数，再「加一个模数、再取模」把结果拉回 [0, m-1]。

易错：只算到内层的 -3 % 7 = -3 就选负值，忽略外面还有 +7 再 %7。

B4选择题

用埃氏筛法求 [2,20] 内的质数，第一个被划掉的合数是（）

A. 4   B. 6   C. 8   D. 9

查看参考答案

答案：A. 4

从最小质数2开始，2的倍数中最小的合数是4，所以4第一个被划掉。

考点：埃氏筛从最小的质数 2 开始，把它的倍数（从 2×2 起）逐个标记为合数，因此最先被划掉的正是 4。

易错：以为从 2×1 开始划，把质数 2 自己也标记成合数。

🔴 C组 · 挑战（4题）

C1初赛真题

正整数 2024 的质因数分解中，所有质因数的和是（）

A. 28   B. 30   C. 34   D. 36

查看参考答案

答案：D. 36

2024 = 2³ × 11 × 23

不同质因数之和 = 2 + 11 + 23 = 36... 等等，重新算：

2024 ÷ 2 = 1012, ÷2 = 506, ÷2 = 253, 253 ÷ 11 = 23

2024 = 2³ × 11 × 23，质因数(去重)之和 = 2+11+23 = 36

若题目问"所有质因数（含重复）之和"= 2+2+2+11+23 = 40

通常指不同质因数之和 = 36，选D。（注：原题选项可能有调整）

考点：质因数分解用「从小到大试除、逐个剥离质因子」的方法，剥离后只需试到剩余部分的平方根即可停手。

易错：把 2³ 中的 2 重复计入和，混淆题目问的是「不同质因数之和」还是「含重复的质因数之和」。

C2初赛真题

若 GCD(a,b)=1，则称a,b互质。以下哪对数互质？（）

A. (6,9)   B. (8,15)   C. (12,18)   D. (14,21)

查看参考答案

答案：B. (8,15)

8=2³, 15=3×5，无公共质因子 → GCD=1 ✅

A: GCD(6,9)=3; C: GCD(12,18)=6; D: GCD(14,21)=7

考点：互质的判定只看 GCD 是否为 1，即两数的质因数集合没有交集，并不要求两个数本身都是质数。

易错：认为互质必须两数都是质数，或只检查两数有没有公因数 2 就下结论。

C3初赛真题

在线性筛中，当 i % primes[j] == 0 时执行 break，其目的是（）

A. 避免数组越界
B. 减少不必要的计算
C. 保证每个合数只被最小质因子筛掉
D. 防止整数溢出

查看参考答案

答案：C

这是线性筛的核心：当 i 能被 primes[j] 整除时，i×primes[j+1] 的最小质因子是 primes[j] 而非 primes[j+1]，继续筛会导致该合数被非最小质因子重复标记。

考点：这一句 break 是线性筛的关键：保证每个合数只被它的「最小质因子」标记一次，从而把总复杂度压到 O(N)。

易错：把 break 理解成「跳过质数」或「提前结束外层循环」，从而误以为筛不完整。

C4初赛真题

满足 5x ≡ 3 (mod 11) 的最小正整数 x 是（）

A. 5   B. 7   C. 9   D. 10

查看参考答案

答案：A. 5

5×7 = 35, 35 mod 11 = 35 - 3×11 = 35-33 = 3 ✅

验证其他：5×5=25≡3? 25-22=3... 等等，25 mod 11 = 3 也对？

重新验算：5×5=25, 25÷11=2余3 → 25≡3(mod 11) ✅

所以 x=5 也满足！但5<7，答案应为 A. 5。

（注：此题需仔细验算，5确实是更小的解）

考点：模意义下「除以 5」等价于乘 5 的乘法逆元 9（因为 5×9 ≡ 1 mod 11），故 x ≡ 3×9 = 27 ≡ 5。

易错：只凭 5×7 = 35 ≡ 3 就锁定 x=7，没有检验更小的解（5×5 = 25 ≡ 3），应从 x=1 起代或用逆元求最小正解。