【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:算术基本定理(唯一分解定理)与约数个数、约数和公式推导
在数论与计数类考题中,许多同学一看到“求 360 有多少个正约数、约数和是多少”或“把一个高达 10^12 的整数拆成质因数乘积”,就陷入了两头踩坑的窘境:手写质因数分解代码时,枚举完 i <= n / i 后忘了补收尾的 if (n > 1),结果在 36 上测试完美...
在数论与计数类考题中,许多同学一看到“求 360 有多少个正约数、约数和是多少”或“把一个高达 的整数拆成质因数乘积”,就陷入了两头踩坑的窘境:手写质因数分解代码时,枚举完 i <= n / i 后忘了补收尾的 if (n > 1),结果在 36 上测试完美通过,一遇上 12、84 或任意大质数就漏掉最大的质因子,交上去喜提满屏 WA;背了约数个数公式 ,却说不清为什么要给每个指数 +1,一旦初赛把问题改成“求 360 的偶数正约数个数”或“恰有 4 个正约数的数长什么样”,立刻凭感觉猜“奇偶各占一半”掉进出题人的陷阱;碰到经典的“1~n 盏灯开关问题”,还在写二重循环硬模拟,殊不知它背后藏着“完全平方数 ⟺ 约数个数为奇数”的秒杀规律!在 GESP 五级认证以及 CSP-J 初复赛中,算术基本定理(唯一分解定理)的本质与 分解模板、由乘法原理推导约数个数与约数和公式、以及完全平方数拥有奇数个约数的核心推论,是将数论与组合计数彻底打通的关键枢纽。本文将从底层逻辑与完整推导出发,把这套数论高频考点一次吃透。
🎯 考纲锚点与核心痛点
📍 对应考点:掌握算术基本定理(唯一分解定理)及 质因数分解代码模板,能基于分步乘法原理独立推导约数个数公式与约数和公式,熟练运用“完全平方数 ⟺ 约数个数为奇数”等核心推论。 🎯 适用等级:
GESP 五级考点 | CSP-J/S 初赛/复赛必考
在历年 GESP 五级与 CSP-J 考场上,考生最常在以下三大痛点上丢分:
- “质因数分解漏写
if (n > 1),被小样例迷惑”:当n的所有质因子都不超过 (如36)时,漏掉收尾判断也能侥幸算对;可一旦剩余的商本身是大质数(如12除完2^2剩3、84除完2^2 * 3剩7),直接丢失最大质因子,导致分解式、约数个数与约数和全盘算错; - “死记公式不解原理,遇变式就抓瞎”:不理解约数个数与约数和背后的“质因子指数独立选法”与“乘法分配律逆用”,求偶数约数个数时误以为直接除以
2,或者忘记每个质因子都可以取0次方导致漏加+1; - “约数和不开
long long或盲目套等比除法公式酿成溢出”:哪怕n = 10^9还在int范围内,其约数和 已超出 32 位有符号整数上限;若用等比求和公式 计算大质数的约数和,中间项 甚至直接撑爆 64 位long long!
🧠 一、 核心原理深度拆解(有理论)
1. 算术基本定理(唯一分解定理)与 质因数分解
算术基本定理(Fundamental Theorem of Arithmetic)指出:任何一个大于 1 的正整数 n,都可以唯一地分解为有限个质数的乘积(不计质因数的排列顺序)。把相同的质因数合并成幂次,即可写成标准分解式:
🤔 高频概念追问:为什么数学上严格规定
1既不是质数,也不是合数? 正是为了守护唯一分解定理的“唯一性”!假如把1当成质数,那么6就可以写成 、、、 等无穷多种形式,唯一分解定理瞬间失效,整座初等数论大厦都会随之崩塌。
把唯一分解定理翻译成 C++11 代码,只需不到 15 行,但藏着两大精妙的数学保证:
void factorize(long long n) {
for (long long i = 2; i <= n / i; i++) {
if (n % i == 0) {
int e = 0;
while (n % i == 0) {
n /= i;
e++;
}
// 找到质因子 i,指数为 e
}
}
if (n > 1) {
// 剩下的 n 必是唯一大于 sqrt(原n) 的质因子,指数为 1
}
}- 为什么
i是逐一递增(2, 3, 4, 5, 6, ...),却绝不会把合数当成质因子输出? 反证法:假设某个合数c(比如4或6)能整除当前的n。因为c是合数,它必有更小的质因数p < c。但在循环走到c之前,早已路过p,并且用while (n % p == 0) n /= p;把n体内所有的因子p彻底抽干了!此时的n根本不再含因子p,自然绝对不可能被c整除。因此,任何进入if (n % i == 0)分支的i必为质数! - 为什么循环条件只写
i <= n / i,最后再补一句if (n > 1)? 核心引理:任意正整数n至多只包含1个大于 的质因数。证明极其简短:倘若存在两个大于 的质因数p和q,则它们的乘积满足 ,与“二者皆为n的因子”矛盾! 因此,当所有不超过 的小质因数都被除尽后,剩下的n只剩两种结局:要么缩成1(分解完毕),要么本身就是那唯一剩下的大质因数(指数必为1)。而且每次除尽因子后n实时变小,循环上界n / i动态收紧,最坏情况(n本身是质数)仅运行 步,时间复杂度严格为 ,同时用i <= n / i彻底消灭了i * i溢出风险。
2. 基于乘法原理推导约数个数公式
设正整数的标准质因数分解为 。由唯一分解定理可知,正整数 d 能整除 n,当且仅当 d 不包含 n 以外的新质因子,且每个质因子的幂次都不超过 n 中对应的幂次:
因此,构造一个正约数 d 等价于完成 k 步彼此独立的决策:
- 决定质因子 取几个:,共有
e1 + 1种选法(别忘了a1 = 0代表“不选 ”); - 决定质因子 取几个:,共有
e2 + 1种选法; - ……
- 决定质因子 取几个:,共有
ek + 1种选法。
根据分步乘法计数原理,正约数总个数 等于各质因子指数加 1 后的连乘积:
以 n = 72 = 2^3 × 3^2 为例,质因子 2 有 3 + 1 = 4 种选法,质因子 3 有 2 + 1 = 3 种选法,它们像棋盘的横纵坐标一样两两配对,不重不漏地生成全部 4 × 3 = 12 个正约数:
========================================================================
【72 = 2^3 × 3^2 的全部正约数生成矩阵(4 行 × 3 列 = 12 个约数)】
│ 3^0 (= 1) │ 3^1 (= 3) │ 3^2 (= 9)
──────────┼──────────────────┼──────────────────┼──────────────────
2^0 (= 1) │ 1 × 1 = 1 │ 1 × 3 = 3 │ 1 × 9 = 9
2^1 (= 2) │ 2 × 1 = 2 │ 2 × 3 = 6 │ 2 × 9 = 18
2^2 (= 4) │ 4 × 1 = 4 │ 4 × 3 = 12 │ 4 × 9 = 36
2^3 (= 8) │ 8 × 1 = 8 │ 8 × 3 = 24 │ 8 × 9 = 72
──────────┴──────────────────┴──────────────────┴──────────────────
▶ 约数个数:行数(3+1) × 列数(2+1) = 4 × 3 = 12
▶ 约数之和:(1 + 2 + 4 + 8) × (1 + 3 + 9) = 15 × 13 = 195
========================================================================3. 乘法分配律逆用:推导约数和公式
盯着上面的 4 × 3 约数矩阵,如果把这 12 个数全部加起来,完全不需要一个个硬算!利用初中就学过的乘法分配律逆用,先把每一行的公因子提出来,再提公共括号:
把连乘积展开后的每一项,恰好唯一对应 n 的一个正约数 ,既无重复,也无遗漏!由此立刻得到一般形式的约数和公式:
代码实现神技:秦九韶迭代累加 sub_sum = sub_sum * p + 1
在程序中计算括号内的等比数列和 时,千万不要套右侧的除法公式 !直接初始化 sub_sum = 1,在 while (n % i == 0) 每次除以 i 的同时执行一行 sub_sum = sub_sum * i + 1; 即可:
- 除第
1次:1 * p + 1 = p + 1 - 除第
2次:(p + 1) * p + 1 = p^2 + p + 1 - 除第
e次:
这种写法不需要多算 (防溢出)、不需要做除法(遇取模题无需模逆元),仅需一行代码就与质因数分解无缝融合!
4. 高频神级推论:完全平方数 ⟺ 约数个数为奇数
在 GESP 和 CSP-J 初赛中,常考这样一类脑筋急转弯:“一个正整数什么时候会有奇数个正约数?”
我们用约数个数公式一击秒杀:
- 乘积 是奇数;
- ⟺ 每一个乘数 全部都是奇数(只要有一个偶数,乘积立马变偶数);
- ⟺ 所有质因子的指数 全部都是偶数(可记作 );
- ⟺ ,即
n必定是一个完全平方数!
从直觉上理解同样优美:正约数总是以 成双成对出现,只有当 n 是完全平方数时,正中间会冒出一个“自己和自己配对”的约数 ,导致总约数个数多出孤零零的 1 个而变成奇数。
| 核心考点 / 结论 | 数学表达式 | 典型应用场景与秒杀技巧 |
|---|---|---|
| 唯一分解定理 | 求 GCD(各质因子指数取 )、求 LCM(各质因子指数取 ) | |
| 约数个数公式 | 统计约数总数、限定条件约数个数(如偶数约数、某个数的倍数约数) | |
| 约数和公式 | 完美数判定()、亲和数判定、大数约数和取模 | |
| 奇偶性推论 | 为奇数 | 经典“1~n 盏开关灯问题”:最终亮着的灯正是 1..n 中的完全平方数,共 盏 |
💡 考场黄金法则:
- 【分解三件套:
i <= n / i+while除尽 +if (n > 1)收尾】:三者缺一不可,时间复杂度严格 且永不溢出、绝不漏大质因子。- 【约数计数抓“指数选法”,约数求和用
sub = sub * p + 1】:把每个质因子看成独立维度(指数+1包含0次方),牢记完全平方数的所有质因子指数全为偶数、恰有奇数个正约数!
🔍 二、 具象代码与数据推演(有举例)
示例:追踪 n = 84 的质因数分解、动态缩界与收尾捕获
下面这段 26 行的标准 C++11 程序对 n = 84()一站式完成质因数分解、约数个数与约数和计算,并实时打印每一步的内存状态变化:
#include <iostream>
using namespace std;
int main() {
long long n = 84;
long long div_cnt = 1, div_sum = 1;
cout << "Start: n=" << n << endl;
for (long long i = 2; i <= n / i; i++) {
if (n % i == 0) {
int e = 0;
long long sub_sum = 1;
while (n % i == 0) {
n /= i;
e++;
sub_sum = sub_sum * i + 1;
}
div_cnt *= (e + 1);
div_sum *= sub_sum;
cout << "Factor " << i << "^" << e
<< " -> rem n=" << n
<< ", cnt=" << div_cnt
<< ", sum=" << div_sum << endl;
}
}
if (n > 1) {
div_cnt *= 2;
div_sum *= (1 + n);
cout << "Tail " << n << "^1"
<< " -> rem n=1"
<< ", cnt=" << div_cnt
<< ", sum=" << div_sum << endl;
}
return 0;
}分步内存变量变化与循环缩界推演表
阶段 / 循环变量 i |
进入前剩余 n |
上界判据 i <= n / i |
内层 while 除尽与 sub_sum 变化 |
更新后 div_cnt |
更新后 div_sum |
|---|---|---|---|---|---|
| 初始状态 | 84 |
— | — | 1 |
1 |
i = 2 |
84 |
2 <= 42(真) |
84 -> 42 -> 21(e = 2),sub_sum: 1 -> 3 -> 7 |
1 * 3 = 3 |
1 * 7 = 7 |
i = 3 |
21 |
3 <= 7(真) |
21 -> 7(e = 1),sub_sum: 1 -> 4 |
3 * 2 = 6 |
7 * 4 = 28 |
i = 4 |
7 |
4 <= 1(假!提前结束) |
退出 for 循环(注意 i 根本没跑到 7!) |
6 |
28 |
收尾 if (n > 1) |
7 |
7 > 1(真) |
捕获残余大质因子 7^1,1 + 7 = 8 |
6 * 2 = 12 |
28 * 8 = 224 |
手算全部正约数核对:84 的全部 12 个正约数为 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84,首尾配对求和 (1+84)+(2+42)+(3+28)+(4+21)+(6+14)+(7+12) = 85+44+31+25+20+19 = 224,完全吻合!
程序经 g++ -O2 -std=c++11 编译运行实际输出:
Start: n=84
Factor 2^2 -> rem n=21, cnt=3, sum=7
Factor 3^1 -> rem n=7, cnt=6, sum=28
Tail 7^1 -> rem n=1, cnt=12, sum=224⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级判断题与 CSP-J 考场上,以下三个边界陷阱最容易让人痛失满分:
❌ 易错点 1:漏写循环后的收尾判断 if (n > 1),被 36 这类样例麻痹!
- 错误代码:
C++· 8 行
for (long long i = 2; i <= n / i; i++) { if (n % i == 0) { int e = 0; while (n % i == 0) { n /= i; e++; } div_cnt *= (e + 1); } } // 致命漏写:缺少 if (n > 1) div_cnt *= 2; - 为什么错:这段错代码极具欺骗性——测
n = 36时,i = 2把36除成9,i = 3恰好满足3 <= 9 / 3把9除成1,输出div_cnt = 9竟然全对!但只要换一个极小的合数n = 12:i = 2把12除成3,下一轮i = 3检查条件3 <= 3 / 3 = 1直接为假并跳出循环,剩下的质因子3被彻底丢弃,错算出d(12) = 3(正解为6);对任意质数(如7、13),更会直接错算出d(p) = 1! - 正确规范:质因数分解的
for循环一结束,条件反射式地紧跟if (n > 1),把残余的大质因子以指数1纳入统计(约数个数乘2,约数和乘1 + n)。
❌ 易错点 2:把 1 当作质数处理,或忘加 +1 混淆“指数乘积”与“约数个数”!
- 错误认知:认为
n = 2^3 × 3^2的约数个数是3 × 2 = 6;或者在特判n = 1时把它输出为质因子1^1,甚至误认为d(1) = 0。 - 为什么错:
- 对 ,每个质因子并非至少选
1个,而是允许选0个(当所有质因子都选0个时,拼出的正是约数1),因此可选方案数是(e_i + 1)而非e_i; 1没有任何质因子(空乘积),它唯一的正约数就是自身1,所以d(1) = 1、sigma(1) = 1——好在我们的代码初始化div_cnt = 1, div_sum = 1,当n = 1时循环和if (n > 1)均不进入,天然正确得出1和1(仅在打印分解式时需特判输出1)。
- 对 ,每个质因子并非至少选
- 正确规范:牢记公式里每一项必须
+1,且1不是质数也不是合数。
❌ 易错点 3:约数和仍用 int 存储,或硬套等比除法公式 (p^(e+1) - 1) / (p - 1) 导致溢出!
- 错误写法:题目给的
n不超过 (放得进int),便顺手声明int div_sum = 1;,或者写(pow(p, e + 1) - 1) / (p - 1)求单组质因子的幂次和。 - 为什么错:
- 约数和远超
n本身:实测n = 1000000000(,完全在int范围内)的正约数和高达2497558338,直接撑爆 32 位int上限2147483647变成负数;甚至质数n = 2147483647的约数和2147483648也会刚好爆int! - 等比公式的分子 爆炸与浮点精度坑:
pow()返回double,超过 会直接丢精度;即便手写整数快速幂算 ,当n是接近 的大质数(e = 1)时,分子 直接冲破long long上限 !
- 约数和远超
- 正确规范:统计约数个数与约数和一律使用
long long,并用纯整数迭代sub_sum = sub_sum * i + 1累加每组等比和,彻底远离pow()、中间大幂次溢出与除法取模难题。
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛高频计算与变式考点:约数个数、偶数约数与约数和综合秒算)
题目:正整数 360 共有多少个正约数?其中偶数正约数有多少个?所有正约数的和是多少?( )
- A.
24个、12个、1170 - B.
24个、18个、1170 - C.
24个、18个、1080 - D.
18个、12个、1170
🔍 答案与逐项排除解析:
- 正确答案:B
- 解析过程:
- 标准质因数分解:。
- 求正约数总个数(排除 D):套用乘法原理公式: 直接排除 D。
- 求偶数正约数个数(排除 A 的头号陷阱!):很多同学凭直觉误以为“约数里奇数、偶数各占一半,所以
24 / 2 = 12”,于是中计错选 A! 正确做法是回到质因子指数选法:一个约数是偶数,当且仅当它至少包含一个质因子2,即2的指数 只能从 里选(3种选法,踢掉 ),而3仍有2 + 1 = 3种选法、5仍有1 + 1 = 2种选法。因此偶数约数个数为: (也可以用补集思维验证:奇数约数不含因子2,个数为 ,故偶数约数为24 - 6 = 18!)由此秒杀排除 A。 - 求全部正约数之和(排除 C):套用约数和公式: 排除 C,稳稳锁定 B。
【例题 2 · 判断题】(GESP 五级数论推论逆向辨析:恰有 4 个正约数的数长什么样?)
题目:如果一个正整数 n 恰有 4 个正约数,那么 n 必然可以表示为两个不同质数的乘积(即形如 ,其中 p 与 q 为不相等的质数)。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 逆推公式拆分漏了情况:由约数个数公式 (其中每个括号都满足 ),把整数
4拆成不小于2的正整数乘积,共有两种合法拆法:- 情况一:,对应两个不同质数的一次幂相乘,即 (例如
6 = 2 × 3、10 = 2 × 5); - 情况二:,对应单个质数的三次方,即 !
- 情况一:,对应两个不同质数的一次幂相乘,即 (例如
- 极简反例:取
n = 8 = 2^3(或27 = 3^3、125 = 5^3)。8的全部正约数为1, 2, 4, 8,恰有4个正约数,但8只有唯一的质因子2,根本无法写成两个不同质数的乘积!因此原命题错误。
- 逆推公式拆分漏了情况:由约数个数公式 (其中每个括号都满足 ),把整数
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛高频母题:多组大整数质因数分解、约数个数与约数和一站式统计)
题目描述:给定 T()组测试数据,每组给出一个正整数 n()。请对每个 n 输出两行结果:
- 第一行:按质因数从小到大的顺序输出
n的标准质因数分解式,每个质因子写作p^e(若指数e == 1则简写为p),相邻项用*连接;特别地,若n == 1,第一行直接输出1; - 第二行:输出两个用空格隔开的整数,依次为
n的正约数个数 与正约数之和 。
输入格式:
第一行包含一个正整数 T,表示测试数据组数。
接下来 T 行,每行包含一个正整数 n。
输出格式: 对于每组数据,输出两行:第一行为标准质因数分解式,第二行为正约数个数和正约数之和。
💡 算法建模与关键细节:
- 数据范围与防溢出:
n最高达 ,必须使用long long读入并计算;循环上限i <= rem / i最多枚举到 ,单组数据最坏 次运算,T <= 100总计不超过 步,远在 1 秒时限内轻松通过; - 迭代求约数和:内层
while每除一次i,顺手执行sub_sum = sub_sum * i + 1,全程不产生大于 的中间值,在 下总约数和 远小于 ,在long long中绝对安全; - 特判
n == 1与收尾if (rem > 1):先特判n == 1输出1与1 1;对n >= 2,循环结束后务必判断rem > 1,把可能残留的大质因子按指数1拼入分解式,并将div_cnt *= 2、div_sum *= (1 + rem)。
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
long long n;
cin >> n;
if (n == 1) {
cout << "1\n1 1\n";
continue;
}
long long rem = n;
long long div_cnt = 1;
long long div_sum = 1;
bool first = true;
for (long long i = 2; i <= rem / i; i++) {
if (rem % i == 0) {
int e = 0;
long long sub_sum = 1;
while (rem % i == 0) {
rem /= i;
e++;
sub_sum = sub_sum * i + 1;
}
if (!first) cout << " * ";
first = false;
cout << i;
if (e > 1) cout << "^" << e;
div_cnt *= (e + 1);
div_sum *= sub_sum;
}
}
if (rem > 1) {
if (!first) cout << " * ";
cout << rem;
div_cnt *= 2;
div_sum *= (1 + rem);
}
cout << "\n" << div_cnt << " " << div_sum << "\n";
}
return 0;
}- 输入样例:
Code· 6 行
5 1 36 84 360 999999999989 - 输出样例:
(样例解释:Code· 10 行
1 1 1 2^2 * 3^2 9 91 2^2 * 3 * 7 12 224 2^3 * 3^2 * 5 24 1170 999999999989 2 9999999999901特判输出1与1 1;36 = 2^2 * 3^2是完全平方数,指数全为偶数,恰有奇数个约数9个,约数和(1+2+4)*(1+3+9) = 91;84与360分别验证了收尾大质因子捕获与多质因子连乘;999999999989是接近 的大质数,循环结束后由if (rem > 1)捕获,迅速得出2个约数且约数和999999999990无溢出。)
看完题解,马上用 240 关实战检验掌握度
覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。
配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。
同专栏相关推荐
【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
OneCoder
始于 2012持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com