专题18 · 数学专题1
数学专题是复赛里最稳的送分点——知识点固定、代码短、不考思维。
本讲四块：整除与约数、欧几里得算法、质数判定、分解质因数与约数个数/和。
每块都配一道真题，把公式变成能跑的代码。
a | b 是什么意思
整除与约数
a | b 表示 a 整除 b，即 b % a == 0。
此时称 a 是 b 的约数，b 是 a 的倍数。
注意：0 不能做除数；任何数都整除 0。
求一个数的所有约数
试除到 √n 即可，因为约数成对出现：
若 d | n，则 (n/d) | n。
每找到一个小约数，就同时得到大约数。
vector<int> d; for (int i = 1; i * i <= n; i++) // ★ 只到 √n if (n % i == 0){ d.push_back(i); if (i != n / i) d.push_back(n / i); // ★ 完全平方数别重复加 } sort(d.begin(), d.end());
i * i 在 n 很大时会溢出 int（用 long long 或写成 i <= n / i）；
② 完全平方数（如 n = 16，i = 4）会重复加入同一个约数，必须判 i != n/i。辗转相除：每步都在缩小
gcd(a, b) = gcd(b, a % b) —— 因为 a 和 b 的公约数集合，与 b 和 a%b 的公约数集合完全相同。
每做一步，数字至少减半，所以复杂度是 O(log n)，n = 10¹⁸ 也只要几十步。三种写法，一个都别错
① 递归
int gcd(int a,int b){
return b ? gcd(b, a%b) : a;
}② 迭代（推荐）
int gcd(int a,int b){
while(b){int t=a%b;a=b;b=t;}
return a;
}③ 三目一行
int gcd(int a,int b){
return b?gcd(b,a%b):a;
} // 同①lcm 与 gcd 的关系（必考）
a × b = gcd(a,b) × lcm(a,b) → lcm(a,b) = a / gcd(a,b) × b
★ 一定要先除后乘：写成 a * b / gcd 时，a*b 可能先溢出；
写成 a / gcd * b 就安全了。
a*b 溢出 → 先除后乘；
② 忘记 b == 0 时返回 a；③ 负数取模在 C++ 里结果仍可能为负，求 gcd 前先取绝对值。把一个数拆成质数连乘
算术基本定理
任何大于 1 的整数都能唯一分解成质数的连乘积：
n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ。
有了这个分解，约数个数、约数和、是否为完全平方数全都能直接算出来。
两个公式怎么来的
约数个数 (e₁+1)(e₂+1)…
每个质因子 p₁ 可以取 0 ~ e₁ 共 e₁+1 种指数，各质因子独立 → 乘法原理相乘。
约数之和 (p⁰+…+p^e₁)×…
把每个质因子的幂次和相乘，展开后每一项正好是一个约数（分配律）。
√n 是分界线
n/i = 6，
两个是同一个 → 只能加一次。漏判就会多输出一个约数。试除法与它的边界
判定模板
bool isPrime(int n){
if (n < 2) return false; // ★ 0、1 都不是质数
for (int i = 2; i * i <= n; i++) // ★ 只到 √n
if (n % i == 0) return false;
return true;
}为什么到 √n 就够
若 n 有大于 √n 的因子 d，那 n/d 必然小于 √n，
也就早就试到了。
所以试到 √n 没找到，就一定是质数。
① 忘记 n < 2
把 1 判成质数 → 分解质因数死循环。
② 循环写成 i < n
n = 10⁹ 时超时（TLE）。
③ i*i 溢出
int 范围内 i*i 可能溢出 → 用 i <= n/i。
把条件翻译成"互质"
推导（三步）
① a × b = gcd × lcm = x0 × y0
② 设 a = x0·p，b = x0·q（a、b 都是 x0 的倍数）
③ 代入得 p·q = y0/x0，且必须 gcd(p,q) = 1
于是问题变成：把 n = y0/x0 拆成两个互质因子，有几种拆法。
样例 x0=3, y0=60
y0 % x0 == 0 ✅ → n = 20
20 的因子对：(1,20) 互质 ✅、(2,10) 不互质 ❌、(4,5) 互质 ✅
(1,20) 和 (20,1) 算两种，(4,5) 和 (5,4) 算两种 → 4。
y0 % x0 != 0 直接除 → n 不是整数，结果全错；
② 忘了 (p,q) 与 (q,p) 是有序对，只计一次 → 答案少一半。"枚举约数"类题目的通用套路
套路
题目要求"找出所有满足某条件的约数"时（如 ABC180C 求 N 的所有约数）：
① 试除到 √N；
② 小的进 小列表，大的进 大列表；
③ 输出 = 小列表升序 + 大列表降序（直接合并就是升序）。
为什么这样最快
暴力从 1 枚举到 N 是 O(N)；成对枚举只要 O(√N)。
N = 10¹² 时，前者要跑 10¹² 次（必 TLE），后者只要 10⁶ 次。
vector<long long> lo, hi; for (long long i = 1; i * i <= n; i++) // ★ i*i 用 long long if (n % i == 0){ lo.push_back(i); if (i != n / i) hi.push_back(n / i); // ★ 平方数去重 } for (long long x : lo) cout << x << '\n'; for (int i = hi.size() - 1; i >= 0; i--) cout << hi[i] << '\n'; // 倒着输出
数学题的五个高频失分点
① a*b 溢出
❌ a*b/gcd ✅ a/gcd*b（先除后乘）。
② 完全平方数重复
❌ 不判 i != n/i → 约数多算一个。
✅ 必须判。
③ 漏掉剩余质因子
❌ 分解质因数后不处理 t > 1 → 少算一个质因子。
✅ if (t > 1) cnt *= 2;
④ i*i 溢出
❌ int 下 i*i 溢出成负数 → 循环条件失效。
✅ i <= n / i 或 long long。
知识树
数学1 ─┬─ 整除与约数（成对枚举，√n 分界）
├─ gcd（辗转相除 O(log n)）／ lcm（先除后乘）
├─ 质数判定（试除到 √n，n < 2 特判）
└─ 算术基本定理 → 分解质因数 → 约数个数 ∏(e+1) ／ 约数和 ∏(p⁰+…+p^e)
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
最大公约数和最小公倍数问题 · GCDLCM
第1档 · 2 分钟x == y → 1 对；y % x != 0 → 0 对
第2档 · 8 分钟
从 1 到 y 枚举 a，算 lcm 比对，y ≤ 10⁵ 稳过
第3档 · 10 分钟
只做 x == 1 的情形（互质对计数）
第4档 · 15 分钟
令 k = y/x，答案 = 2^(k 的不同质因子个数)
约数个数与约数之和 · DIVCNT
第1档 · 2 分钟n == 1 → 1 个、和为 1
第2档 · 8 分钟
从 1 到 n 枚举判整除，n ≤ 10⁴ 稳过
第3档 · 10 分钟
只做约数个数（不做约数之和）
第4档 · 15 分钟
分解质因数 n = Π pᵢ^aᵢ；个数 = Π(aᵢ+1)，和 = Π(1+p+…+p^a)
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。五道题
① gcd(48, 18) = ?
② lcm 的正确写法是？
③ 30 的约数个数与约数和是？
④ 求 n 的所有约数，循环条件应写成？
a*b/gcd 在小数据时和正解完全一致，只有大数才溢出，属于"本地过了、提交 WA"的典型，
正好用来讲"先除后乘"这条工程习惯。