【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:算术基本定理(唯一分解定理)与约数个数、约数和公式推导

所属专题GESP 五级
核心标签GESP
代码 / 阅读C++11 · 34 min
累计阅读实时统计
TL;DR · 核心摘要

在数论与计数类考题中,许多同学一看到“求 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 考场上,考生最常在以下三大痛点上丢分:

  1. “质因数分解漏写 if (n > 1),被小样例迷惑”:当 n 的所有质因子都不超过 (如 36)时,漏掉收尾判断也能侥幸算对;可一旦剩余的商本身是大质数(如 12 除完 2^2 剩 3、84 除完 2^2 * 3 剩 7),直接丢失最大质因子,导致分解式、约数个数与约数和全盘算错;
  2. “死记公式不解原理,遇变式就抓瞎”:不理解约数个数与约数和背后的“质因子指数独立选法”与“乘法分配律逆用”,求偶数约数个数时误以为直接除以 2,或者忘记每个质因子都可以取 0 次方导致漏加 +1;
  3. “约数和不开 long long 或盲目套等比除法公式酿成溢出”:哪怕 n = 10^9 还在 int 范围内,其约数和 已超出 32 位有符号整数上限;若用等比求和公式 计算大质数的约数和,中间项 甚至直接撑爆 64 位 long long!

🧠 一、 核心原理深度拆解(有理论)

1. 算术基本定理(唯一分解定理)与 质因数分解

算术基本定理(Fundamental Theorem of Arithmetic)指出:任何一个大于 1 的正整数 n,都可以唯一地分解为有限个质数的乘积(不计质因数的排列顺序)。把相同的质因数合并成幂次,即可写成标准分解式:

🤔 高频概念追问:为什么数学上严格规定 1 既不是质数,也不是合数? 正是为了守护唯一分解定理的“唯一性”!假如把 1 当成质数,那么 6 就可以写成 、、、 等无穷多种形式,唯一分解定理瞬间失效,整座初等数论大厦都会随之崩塌。

把唯一分解定理翻译成 C++11 代码,只需不到 15 行,但藏着两大精妙的数学保证:

C++· 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
    }
}
  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 必为质数!
  2. 为什么循环条件只写 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 个正约数:

Code· 13 行
========================================================================
【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 中的完全平方数,共 盏

💡 考场黄金法则:

  1. 【分解三件套:i <= n / i + while 除尽 + if (n > 1) 收尾】:三者缺一不可,时间复杂度严格 且永不溢出、绝不漏大质因子。
  2. 【约数计数抓“指数选法”,约数求和用 sub = sub * p + 1】:把每个质因子看成独立维度(指数 +1 包含 0 次方),牢记完全平方数的所有质因子指数全为偶数、恰有奇数个正约数!

🔍 二、 具象代码与数据推演(有举例)

示例:追踪 n = 84 的质因数分解、动态缩界与收尾捕获

下面这段 26 行的标准 C++11 程序对 n = 84()一站式完成质因数分解、约数个数与约数和计算,并实时打印每一步的内存状态变化:

C++· 34 行
#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 编译运行实际输出:

Code· 4 行
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. 对 ,每个质因子并非至少选 1 个,而是允许选 0 个(当所有质因子都选 0 个时,拼出的正是约数 1),因此可选方案数是 (e_i + 1) 而非 e_i;
    2. 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) 求单组质因子的幂次和。
  • 为什么错:
    1. 约数和远超 n 本身:实测 n = 1000000000(,完全在 int 范围内)的正约数和高达 2497558338,直接撑爆 32 位 int 上限 2147483647 变成负数;甚至质数 n = 2147483647 的约数和 2147483648 也会刚好爆 int!
    2. 等比公式的分子 爆炸与浮点精度坑: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
  • 解析过程:
    1. 标准质因数分解:。
    2. 求正约数总个数(排除 D):套用乘法原理公式: 直接排除 D。
    3. 求偶数正约数个数(排除 A 的头号陷阱!):很多同学凭直觉误以为“约数里奇数、偶数各占一半,所以 24 / 2 = 12”,于是中计错选 A! 正确做法是回到质因子指数选法:一个约数是偶数,当且仅当它至少包含一个质因子 2,即 2 的指数 只能从 里选(3 种选法,踢掉 ),而 3 仍有 2 + 1 = 3 种选法、5 仍有 1 + 1 = 2 种选法。因此偶数约数个数为: (也可以用补集思维验证:奇数约数不含因子 2,个数为 ,故偶数约数为 24 - 6 = 18!)由此秒杀排除 A。
    4. 求全部正约数之和(排除 C):套用约数和公式: 排除 C,稳稳锁定 B。

【例题 2 · 判断题】(GESP 五级数论推论逆向辨析:恰有 4 个正约数的数长什么样?)

题目:如果一个正整数 n 恰有 4 个正约数,那么 n 必然可以表示为两个不同质数的乘积(即形如 ,其中 p 与 q 为不相等的质数)。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 逆推公式拆分漏了情况:由约数个数公式 (其中每个括号都满足 ),把整数 4 拆成不小于 2 的正整数乘积,共有两种合法拆法:
      • 情况一:,对应两个不同质数的一次幂相乘,即 (例如 6 = 2 × 3、10 = 2 × 5);
      • 情况二:,对应单个质数的三次方,即 !
    2. 极简反例:取 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。

输出格式: 对于每组数据,输出两行:第一行为标准质因数分解式,第二行为正约数个数和正约数之和。

💡 算法建模与关键细节:

  1. 数据范围与防溢出:n 最高达 ,必须使用 long long 读入并计算;循环上限 i <= rem / i 最多枚举到 ,单组数据最坏 次运算,T <= 100 总计不超过 步,远在 1 秒时限内轻松通过;
  2. 迭代求约数和:内层 while 每除一次 i,顺手执行 sub_sum = sub_sum * i + 1,全程不产生大于 的中间值,在 下总约数和 远小于 ,在 long long 中绝对安全;
  3. 特判 n == 1 与收尾 if (rem > 1):先特判 n == 1 输出 1 与 1 1;对 n >= 2,循环结束后务必判断 rem > 1,把可能残留的大质因子按指数 1 拼入分解式,并将 div_cnt *= 2、div_sum *= (1 + rem)。
C++· 45 行
#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 999999999990
    (样例解释:1 特判输出 1 与 1 1;36 = 2^2 * 3^2 是完全平方数,指数全为偶数,恰有奇数个约数 9 个,约数和 (1+2+4)*(1+3+9) = 91;84 与 360 分别验证了收尾大质因子捕获与多质因子连乘;999999999989 是接近 的大质数,循环结束后由 if (rem > 1) 捕获,迅速得出 2 个约数且约数和 999999999990 无溢出。)
OneCoder 信奥远征平台 · oi.coderli.com

看完题解,马上用 240 关实战检验掌握度

覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。

立即闯关
开源代码与考纲字典

配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。

技术交流与考级答疑

欢迎加入 C++ GESP/CSP 群(688906745) 或 Java/Python 群(982860385)。

同专栏相关推荐

OneCoder

OneCoder

始于 2012

持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com

读者讨论与留言

共 0 条讨论
邮箱仅用于接收回复通知,不对外展示
还没有读者留言,欢迎写下你的第一条交流笔记。