Appearance
第2章 初等数论
🎯 本章学习目标
通过本章的学习，你将能够：
- 理解素数与合数：掌握素数的定义，能熟练使用试除法判断素数
- 掌握 GCD/LCM：熟练运用辗转相除法求最大公约数和最小公倍数
- 理解模运算：掌握加减乘的模运算性质，能正确处理取模问题
- 掌握质因数分解：理解唯一分解定理，能对正整数进行质因数分解
- 熟练埃氏筛法：理解埃氏筛的原理，能手写代码，能分析时间复杂度
- 掌握线性筛法：理解欧拉筛的优化思路，掌握 break 的作用和位置
- 计算约数个数与和：利用唯一分解定理推导约数个数和约数和公式
- 分析奇偶性：掌握奇偶运算规律，能用奇偶性分析快速解题
- 区分两种筛法：清楚埃氏筛和线性筛的区别与优劣
- 应对真题题型：能解决选择、判断、代码填空等各类数论题目
🗺️ 本章知识图谱
初等数论
├── 素数与合数
│ ├── 定义（素数/合数/1的特殊性）
│ ├── 素数判定
│ │ ├── 试除法（O(√n)）
│ │ └── 优化（只查奇数、i<=n/i防溢出）
│ ├── 埃氏筛法
│ │ ├── 原理：素数标记倍数
│ │ ├── 复杂度：O(n log log n)
│ │ └── 优化：从 i² 开始标记
│ └── 线性筛法（欧拉筛）
│ ├── 原理：每个合数被最小质因子筛掉
│ ├── 复杂度：O(n)
│ └── 关键：i%primes[j]==0 时 break
├── 约数与倍数
│ ├── GCD 最大公约数
│ │ ├── 辗转相除法
│ │ └── gcd(a,b) = gcd(b, a%b)
│ ├── LCM 最小公倍数
│ │ └── lcm = a / gcd * b（先除后乘防溢出）
│ └── 重要公式：gcd × lcm = a × b
├── 模运算
│ ├── 加法模：(a+b)%m = ((a%m)+(b%m))%m
│ ├── 减法模：(a-b)%m = ((a%m)-(b%m)+m)%m
│ ├── 乘法模：(a×b)%m = ((a%m)×(b%m))%m
│ └── 注意：减法要加 m 防负数
├── 质因数分解
│ ├── 唯一分解定理
│ ├── 试除法分解
│ ├── 约数个数 = Π(ai+1)
│ └── 约数和 = Π(1+p+p²+...+p^ai)
└── 奇偶性分析
├── 奇偶判断（n%2==1 / n&1）
├── 奇偶运算规律
└── 2的幂判断（n&(n-1)==0）一、素数与合数
1.1 基本定义
- 素数（质数）：大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除。
- 合数：大于 1 的自然数，除了 1 和自身外还有其他因数。
- 1 既不是素数也不是合数，这是最经典的判断题陷阱 ⚠️
- 2 是最小的素数，也是唯一的偶素数
高频考点 ⚠️： 考试常出判断题——"所有素数都是奇数"（错，2是反例）；"1是素数"（错）。
1.2 素数判断——试除法
核心思路： 若 n 是合数，则一定存在一个因数 ≤ √n。因此只需检查 2 到 √n 之间的数能否整除 n。
时间复杂度： O(√n)
cpp
#include <iostream>
using namespace std;
// 判断n是否为素数
bool isPrime(int n) {
if (n < 2) return false; // 小于2不是素数
if (n == 2) return true; // 2是素数
if (n % 2 == 0) return false; // 偶数（除2外）不是素数
for (int i = 3; i <= n / i; i += 2) { // i*i可能溢出，用i<=n/i更安全
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
cout << (isPrime(n) ? "Yes" : "No") << endl;
return 0;
}易错点 ⚠️： 循环条件写
i * i <= n在 n 较大时可能整数溢出！推荐写i <= n / i。另外，从 3 开始只检查奇数可以减少一半循环。
考试常见考法： 给定一个数判断是否为素数；找出某个范围内所有素数的个数。
二、最大公约数与最小公倍数
2.1 欧几里得算法（辗转相除法）
核心公式： gcd(a, b) = gcd(b, a % b)，直到 b = 0 时，a 就是最大公约数。
原理： 设 a = q×b + r（r = a%b），则 a 和 b 的所有公约数也是 b 和 r 的公约数，反之亦然。
递归写法
cpp
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}迭代写法
cpp
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}注意： C++17 的
<numeric>头文件提供了std::gcd，但GESP考试环境可能不支持，务必手写！
2.2 最小公倍数 LCM
核心公式： lcm(a, b) = a / gcd(a, b) * b
易错点 ⚠️： 必须先除后乘！写成
a * b / gcd(a, b)在 a、b 较大时会溢出。先除以 gcd 再乘，可以有效避免中间结果过大。
cpp
int lcm(int a, int b) {
return a / gcd(a, b) * b; // 先除后乘防溢出
}2.3 完整示例
cpp
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int main() {
int a = 12, b = 18;
cout << "gcd(" << a << "," << b << ") = " << gcd(a, b) << endl; // 6
cout << "lcm(" << a << "," << b << ") = " << lcm(a, b) << endl; // 36
return 0;
}考试常见考法： 直接计算 gcd/lcm；利用 gcd×lcm = a×b 的关系进行公式推导；分数化简（分子分母同除 gcd）。
三、同余与模运算
3.1 基本性质
模运算满足以下分配律（假设所有运算在模 m 意义下）：
| 运算 | 公式 |
|---|---|
| 加法 | (a + b) % m = ((a % m) + (b % m)) % m |
| 减法 | (a - b) % m = ((a % m) - (b % m) + m) % m |
| 乘法 | (a * b) % m = ((a % m) * (b % m)) % m |
关键提醒 ⚠️： 模运算没有直接的除法分配律！
(a / b) % m ≠ ((a%m) / (b%m)) % m，除法需要用逆元（五级一般不深入考逆元）。
3.2 防溢出的模运算写法
📚 拓展 · 超纲：快速幂（反复平方法）属提高内容，五级考纲只要求"快速幂思想入门"，不要求独立实现；了解其 O(log n) 的折半思想即可。
cpp
#include <iostream>
using namespace std;
const int MOD = 1000000007;
// 安全的模加法
long long addMod(long long a, long long b) {
return (a % MOD + b % MOD) % MOD;
}
// 安全的模乘法（中间结果可能超出int范围，用long long）
long long mulMod(long long a, long long b) {
return (a % MOD) * (b % MOD) % MOD;
}
// 安全的模减法（加MOD避免负数）
long long subMod(long long a, long long b) {
return ((a % MOD - b % MOD) % MOD + MOD) % MOD;
}
// 快速幂：计算 base^exp % mod，时间O(log exp)
long long fastPow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod; // 指数为奇数，乘到结果
base = base * base % mod; // 底数平方
exp >>= 1; // 指数右移一位（等价于 exp /= 2）
}
return result;
}
int main() {
cout << addMod(500000000, 600000000) << endl; // 1100000000 % MOD = 99999993
cout << fastPow(2, 10, 1000) << endl; // 1024 % 1000 = 24
return 0;
}高频考点 ⚠️： 减法取模必须加 m 再取模，因为 C++ 中负数取模结果为负（如
-3 % 5 = -3），这是最容易丢分的细节！
考试常见考法： 大数取模（如求 2^100 的末几位）；斐波那契数列取模；同余方程的简单判断。
四、质因数分解
4.1 唯一分解定理（算术基本定理）
每个大于 1 的正整数，都可以唯一表示为素数的乘积：
其中 p₁ < p₂ < ... < pₖ 为素数，aᵢ 为正整数。
示例： 360 = 2³ × 3² × 5¹
4.2 试除法分解
cpp
#include <iostream>
using namespace std;
// 对n进行质因数分解，输出每个质因子及其指数
void factorize(int n) {
// 从2开始试除
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
cout << i << "^" << cnt;
if (n > 1) cout << " * ";
}
}
// 如果最后剩余的n>1，说明它本身是一个质因子
if (n > 1) cout << n << "^1";
cout << endl;
}
int main() {
factorize(360); // 输出: 2^3 * 3^2 * 5^1
factorize(17); // 输出: 17^1
factorize(1); // 无输出（1没有质因子）
return 0;
}易错点 ⚠️： 循环结束后，如果 n > 1，剩余的 n 一定是一个素数，必须输出，否则会漏掉最大的质因子。
考试常见考法： 给定数进行质因数分解；根据唯一分解定理求约数个数和约数和。
五、埃氏筛法（Eratosthenes）
5.1 原理
要筛出 [2, n] 中所有素数：
- 从 2 开始，将每个素数 p 的倍数（2p, 3p, 4p, ...）标记为合数
- 未被标记的数就是素数
时间复杂度： O(n log log n)
5.2 完整代码
cpp
#include <iostream>
#include <vector>
using namespace std;
// 埃氏筛法：筛出[2, n]中的所有素数
vector<int> eratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n / i; i++) {
if (isPrime[i]) {
// 将i的所有倍数标记为合数，从i*i开始（更小的已被之前的素数筛掉）
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.push_back(i);
}
return primes;
}
int main() {
int n = 30;
vector<int> primes = eratosthenes(n);
cout << n << " 以内的素数: ";
for (int p : primes) cout << p << " ";
cout << endl;
// 输出: 2 3 5 7 11 13 17 19 23 29
return 0;
}原理说明： 为什么内层从 i² 开始？因为 i×2, i×3, ..., i×(i-1) 已经被更小的素数 2, 3, ..., i-1 筛过了，无需重复。
易错点 ⚠️： 外层循环只需到 √n（即
i <= n/i），因为如果 n 有大于 √n 的因子，那它一定有一个小于 √n 的因子，已经被筛掉了。
考试常见考法： 补全筛法代码；分析筛法时间复杂度；判断某个数是否被筛去。
六、线性筛法（欧拉筛）
6.1 为什么需要线性筛？
埃氏筛中，一个合数可能被多个素数重复标记（如 12 同时被 2 和 3 标记）。线性筛保证每个合数只被它的最小质因子筛去恰好一次，时间复杂度降为 O(n)。
6.2 核心原理
维护一个素数列表，对每个数 i：
- 如果 i 未被标记，将其加入素数列表
- 遍历素数列表中的每个素数 p：
- 标记
i * p为合数 - 如果 i % p == 0，立即 break（关键！保证每个合数只被最小质因子筛去）
- 标记
为什么 break？ 当 i % p == 0 时，p 是 i 的最小质因子。此时 i × 下一个素数 q 的最小质因子是 p（不是 q），它应该在 i 更大时由 p 筛去，而非现在由 q 筛去。
6.3 完整代码
cpp
#include <iostream>
#include <vector>
using namespace std;
// 线性筛法（欧拉筛）：筛出[2, n]中的所有素数
vector<int> eulerSieve(int n) {
vector<bool> isPrime(n + 1, true);
vector<int> primes; // 存储筛出的素数
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push_back(i); // i是素数，加入列表
}
// 用已有的素数去筛合数
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = false;
// 关键：保证每个合数只被最小质因子筛去
if (i % primes[j] == 0) break;
}
}
return primes;
}
int main() {
int n = 30;
vector<int> primes = eulerSieve(n);
cout << n << " 以内的素数: ";
for (int p : primes) cout << p << " ";
cout << endl;
// 输出: 2 3 5 7 11 13 17 19 23 29
return 0;
}以 12 为例理解 break 机制：
- i = 6 时，primes = [2, 3, 5]
- 标记 6×2 = 12 为合数
- 6 % 2 == 0 → break！不会用 3 去标记 6×3 = 18
- 18 会在 i = 9 时，由 9×2 = 18 筛去（2 是 18 的最小质因子）
高频考点 ⚠️： 线性筛的
if (i % primes[j] == 0) break是核心语句，考试常考代码填空！务必理解其含义。
考试常见考法： 补全线性筛代码；比较埃氏筛和线性筛的复杂度；分析某个合数是被哪个素数筛去的。
七、约数与倍数
7.1 约数个数公式
根据唯一分解定理 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，n 的正约数个数为：
原理： 对每个质因子 pᵢ，可以选择 0 到 aᵢ 个（共 aᵢ+1 种选择），各质因子独立，乘法原理。
示例： 360 = 2³ × 3² × 5¹ → 约数个数 = (3+1)(2+1)(1+1) = 24
7.2 约数和公式
n 的所有正约数之和为：
示例： 12 = 2² × 3¹ → 约数和 = (1+2+4)(1+3) = 7×4 = 28（验证：1+2+3+4+6+12 = 28 ✅）
7.3 完整代码
cpp
#include <iostream>
using namespace std;
// 求n的约数个数
int divisorCount(int n) {
int ans = 1;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
ans *= (cnt + 1); // 每个质因子贡献(cnt+1)种选择
}
}
if (n > 1) ans *= 2; // 剩余质因子指数为1，贡献(1+1)=2
return ans;
}
// 求n的约数和
long long divisorSum(int n) {
long long ans = 1;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
long long term = 1; // 等比数列和: 1 + p + p^2 + ... + p^a
long long power = 1;
while (n % i == 0) {
n /= i;
power *= i;
term += power;
}
ans *= term;
}
}
if (n > 1) ans *= (1 + n); // 剩余质因子，等比和为1+n
return ans;
}
int main() {
int n = 360;
cout << n << " 的约数个数: " << divisorCount(n) << endl; // 24
cout << n << " 的约数和: " << divisorSum(n) << endl; // 1170
return 0;
}易错点 ⚠️： 约数和公式中，每个等比数列是从 p⁰=1 开始的，不要漏掉 1！代码中
term初始化为 1 就是这个原因。
考试常见考法： 给定质因数分解式，求约数个数或约数和；求某个范围内约数个数最多的数。
八、奇偶性分析
8.1 基本性质
| 运算 | 结果 |
|---|---|
| 奇 ± 奇 = 偶 | 偶 ± 偶 = 偶 |
| 奇 ± 偶 = 奇 | 奇 × 奇 = 奇 |
| 偶 × 任何 = 偶 | 奇² = 奇，偶² = 偶 |
8.2 编程中的奇偶判断
cpp
// 方法1：取模运算（最直观）
if (n % 2 == 0) { /* 偶数 */ }
else { /* 奇数 */ }
// 方法2：位运算（更高效，考试常考）
if (n & 1) { /* 奇数 */ }
else { /* 偶数 */ }原理： 二进制最低位为 1 则是奇数，为 0 则是偶数。
n & 1就是取最低位。
8.3 奇偶性应用示例
cpp
#include <iostream>
using namespace std;
// 判断n是否为2的幂（2的幂的二进制只有一个1）
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// 交换两个数（不使用临时变量，利用异或）
void swapNum(int& a, int& b) {
a ^= b;
b ^= a;
a ^= b;
}
int main() {
cout << isPowerOfTwo(16) << endl; // 1 (true)
cout << isPowerOfTwo(12) << endl; // 0 (false)
int x = 3, y = 7;
swapNum(x, y);
cout << x << " " << y << endl; // 7 3
return 0;
}考试常见考法： 利用奇偶性快速排除错误选项；位运算判断奇偶；2的幂的判断（
n & (n-1) == 0）。
九、📝 实战练习
练习题 1（单选题）
题目： 用线性筛法筛出 2~20 的所有素数时，合数 12 是在 i 等于几的时候被筛去的？（ ）
A. i = 3 B. i = 4 C. i = 6 D. i = 12
🔑 点击查看答案与解析
答案： C
解析： 根据线性筛原理，每个合数只被它的最小质因子筛去。12 的最小质因子是 2，因此 12 由 i × 2 = 12 筛去，即 i = 6。
验证 i = 6 时：
- primes = [2, 3, 5, ...]
- 标记 6 × 2 = 12 为合数
- 6 % 2 == 0 → break
i = 4 时，4 × 2 = 8（筛去 8），4 % 2 == 0 就 break 了，不会筛到 12。
题目： 已知正整数 n = 2³ × 3² × 5¹ × 7¹，下列说法正确的有（ ）
① n 的约数个数为 48 ② n 的约数和为 (1+2+4+8)(1+3+9)(1+5)(1+7) ③ n 是偶数 ④ n 的所有质因子之和为 17
A. ①② B. ①②③ C. ②③④ D. ①②③④
🔑 点击查看答案与解析
答案： D
解析：
- ① 正确 ✅ 约数个数 = (3+1)(2+1)(1+1)(1+1) = 4×3×2×2 = 48
- ② 正确 ✅ 约数和 = (1+2+4+8)(1+3+9)(1+5)(1+7) = 15×13×6×8 = 9360
- ③ 正确 ✅ n 含因子 2，必为偶数
- ④ 正确 ✅ 所有质因子之和 = 2+3+5+7 = 17
四项全部正确，选 D。
练习题 3（单选题）
题目： 下列关于筛法的叙述，错误的是（ ）
A. 埃氏筛法的时间复杂度为 O(n log log n) B. 线性筛法中每个合数恰好被筛去一次 C. 埃氏筛法中，合数 12 只会被素数 2 标记一次 D. 线性筛法中，当 i % primes[j] == 0 时需要 break，是为了保证合数只被最小质因子筛去
🔑 点击查看答案与解析
答案： C
解析：
- A 正确 ✅ 埃氏筛复杂度为 O(n log log n)
- B 正确 ✅ 线性筛的核心保证就是每个合数只被筛一次
- C 错误 ❌ 埃氏筛中 12 会被素数 2（筛 2 的倍数时）和素数 3（筛 3 的倍数时）重复标记，这正是埃氏筛不如线性筛高效的原因
- D 正确 ✅ break 确保不会用更大的质因子去筛应被更小质因子筛去的合数
选 C。
练习题 4（单选题）
题目： 用辗转相除法求 gcd(48, 18) 的过程中，第二次递归调用时参数是？（ ）
A. gcd(18, 12)
B. gcd(12, 6)
C. gcd(18, 6)
D. gcd(12, 0)
🔑 点击查看答案与解析
答案： B
解析：
辗转相除法的过程：
- 初始：gcd(48, 18) —— 第 0 次
- 第 1 次：gcd(18, 48%18) = gcd(18, 12)
- 第 2 次：gcd(12, 18%12) = gcd(12, 6)
- 第 3 次：gcd(6, 12%6) = gcd(6, 0) → 返回 6
第二次递归调用是 gcd(12, 6)，选 B。
💡 记忆技巧：每次把第二个数当第一个，余数当第二个，直到余数为 0。就像滚雪球——越滚越小，直到归零。
练习题 5（单选题）
题目： (17 - 25) % 7 的结果是？（ ）
A. -8
B. -1
C. 6
D. 1
🔑 点击查看答案与解析
答案： B
解析：
直接计算：17 - 25 = -8。在 C++（GESP 考试语言） 中，% 的结果符号与被除数相同（C++11 起标准规定 a % b 的符号同 a），所以 -8 % 7 = -1，选 B。
⚠️ 易错点：很多人按"数学取模"得到 6（Python 等语言确实如此，因为数学取模结果非负），但 C++ 的
%是"取余"而非"取模"，负数结果也为负数，不是"取决于编译器"（C++11 起标准已固定为与被除数同号）。如果题目要的是非负余数，才需要手动加模：(-8 % 7 + 7) % 7 = 6。务必看清题目问的是 C++ 表达式的值（= -1）还是"非负余数"（= 6）。
练习题 6（判断题）
题目： 对正整数 n 进行质因数分解时，如果循环到 √n 结束后 n 仍然大于 1，说明剩下的 n 本身是一个素数。（ ）
🔑 点击查看答案与解析
答案： 正确 ✅
解析： 这是质因数分解的一个重要结论。
假设循环结束后 n > 1 且 n 是合数，那么 n 至少有两个质因子 p 和 q（p ≤ q），则 p × q ≤ n，因此 p ≤ √n。但我们已经把 ≤ √n 的所有因子都除完了，矛盾。所以剩下的 n 一定是素数。
🍎 生活比喻：就像剥洋葱——你一层一层剥到中心（√n），如果最后还剩一大块，那这块本身就是完整的一层（素数）。
练习题 7（单选题）
题目： 360 = 2³ × 3² × 5¹，它的约数个数是？（ ）
A. 6
B. 12
C. 24
D. 36
🔑 点击查看答案与解析
答案： C
解析：
约数个数公式：如果 n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k，则约数个数 = (a₁+1)(a₂+1)...(a_k+1)
代入 360 = 2³ × 3² × 5¹：
- 约数个数 = (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24
选 C。
💡 为什么是 +1？因为每个质因子的指数可以选 0 到 a_i 共 a_i+1 种选法。比如 2³，可以选 2⁰、2¹、2²、2³ 共 4 种。
练习题 8（单选题）
题目： 以下函数的功能是？（ ）
cpp
bool check(int n) {
return (n & (n - 1)) == 0;
}A. 判断 n 是否为奇数
B. 判断 n 是否为偶数
C. 判断 n 是否为 2 的幂
D. 判断 n 是否为素数
🔑 点击查看答案与解析
答案： C
解析：
这是经典的"判断 2 的幂"位运算技巧。
原理：如果 n 是 2 的幂，那么它的二进制只有一个 1，比如：
- n = 8 → 1000
- n-1 = 7 → 0111
- n & (n-1) = 0000 = 0
如果 n 不是 2 的幂，二进制有多个 1，比如：
- n = 6 → 110
- n-1 = 5 → 101
- n & (n-1) = 100 ≠ 0
选 C。
⚠️ 注意：n = 0 时，0 & (-1) = 0 也成立，但 0 不是 2 的幂。实际使用时要加 n > 0 的判断。
十、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 素数定义（1不是素数、2是唯一偶素数） | ⭐⭐⭐ | 选择/判断 | 判断题陷阱多 |
| 素数判定（试除法） | ⭐⭐⭐⭐ | 选择/代码填空 | i*i 溢出；漏掉 n<2 判断 |
| 埃氏筛法 | ⭐⭐⭐⭐ | 代码填空/选择 | 内层从 i² 开始；复杂度 O(n log log n) |
| 线性筛法 | ⭐⭐⭐⭐⭐ | 代码填空/选择 | break 的位置和作用（核心考点） |
| GCD 辗转相除法 | ⭐⭐⭐⭐⭐ | 选择/程序阅读 | 终止条件 b==0；gcd(0,x)=x |
| LCM 计算 | ⭐⭐⭐⭐ | 选择/计算 | 先除后乘防溢出 |
| gcd × lcm = a × b | ⭐⭐⭐⭐⭐ | 选择/判断/计算 | 公式记错 |
| 模运算（加减乘） | ⭐⭐⭐⭐ | 选择/代码填空 | 减法取模要加 m 防负数 |
| 质因数分解 | ⭐⭐⭐⭐ | 选择/程序填空 | 循环后漏掉 n>1 的素数 |
| 约数个数公式 | ⭐⭐⭐ | 选择/计算 | 是 (ai+1) 不是 ai |
| 约数和公式 | ⭐⭐⭐ | 选择/计算 | 等比和从 1 开始 |
| 奇偶性分析 | ⭐⭐ | 选择/判断 | n&1 判断；2的幂判断 |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 初等数论 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. 素数：大于1，只有1和自身两个因数 │
│ 2. 1既不是素数也不是合数，2是唯一偶素数 │
│ 3. 试除法判断素数：检查到 √n 即可 │
│ 4. 循环条件写 i <= n/i，防止 i*i 溢出 │
│ 5. 辗转相除法：gcd(a,b) = gcd(b, a%b) │
│ 6. 终止条件：b == 0 时返回 a │
│ 7. gcd(a,b) × lcm(a,b) = a × b │
│ 8. 求 LCM 先除后乘：a/gcd*b，防溢出 │
│ 9. 模运算：加减乘都可以分步取模 │
│ 10. 减法取模要加 m：((a-b)%m+m)%m │
│ 11. 埃氏筛：素数标记倍数，O(n log log n) │
│ 12. 线性筛：每个合数被最小质因子筛一次 │
│ 13. 线性筛关键：i%primes[j]==0 就 break │
│ 14. 约数个数：各指数+1 后相乘 │
│ 15. 2的幂判断：n>0 且 n&(n-1)==0 │
└─────────────────────────────────────────────┘