1. 引言为什么需要算数基本定理在算法竞赛和编程面试中数论问题常常是区分选手水平的关键。而算数基本定理Fundamental Theorem of Arithmetic作为数论的基石之一为我们理解和解决一大类整数分解、约数、最大公约数、最小公倍数等问题提供了强大的理论武器。掌握它就如同掌握了打开数论问题宝库的钥匙。本文将用“流食般投喂”的方式从零开始带你彻底吃透算数基本定理并辅以多道经典 OJOnline Judge题目进行实战演练确保你不仅能理解理论更能将其转化为解决实际问题的代码能力。2. 算数基本定理定义与理解定理内容任何一个大于 1 的自然数 N都可以唯一地分解成有限个质数的乘积。用数学公式表示为N p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ其中p₁, p₂, ..., pₖ是质数p₁ p₂ ... pₖa₁, a₂, ..., aₖ是正整数。“唯一”的含义如果不考虑质因数的排列顺序这种分解方式是唯一的。例如12 2² * 3而不能是 2 * 2 * 3 以外的其他质数组合。3. 核心推论与应用方向从算数基本定理可以直接推导出许多重要结论这些结论是解题的关键正约数个数若N p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ则 N 的正约数个数为d(N) (a₁ 1) * (a₂ 1) * ... * (aₖ 1)。正约数之和N 的所有正约数之和为σ(N) (1 p₁ p₁² ... p₁^a₁) * ... * (1 pₖ pₖ² ... pₖ^aₖ)。最大公约数 (GCD) 与最小公倍数 (LCM)将两数分别质因数分解后GCD 取各质因数指数的最小值LCM 取各质因数指数的最大值。判断整除关系若 A 能整除 B则 A 的质因数分解是 B 的质因数分解的子集即 A 的每个质因数的指数都不大于 B 中对应质因数的指数。4. C 实现质因数分解算法的核心是试除法。我们从最小的质数 2 开始逐个尝试去除 N。#include iostream #include vector #include map using namespace std; // 返回一个映射键为质因数值为对应的指数 mapint, int primeFactorization(int n) { mapint, int factors; // 处理因子 2 while (n % 2 0) { factors[2]; n / 2; } // 处理奇数因子 for (int i 3; i * i n; i 2) { while (n % i 0) { factors[i]; n / i; } } // 如果最后剩下的 n 是大于 2 的质数 if (n 1) { factors[n]; } return factors; } int main() { int num 360; // 360 2^3 * 3^2 * 5 mapint, int factors primeFactorization(num); cout num ; bool first true; for (auto [prime, exp] : factors) { if (!first) cout * ; cout prime ^ exp; first false; } cout endl; return 0; }复杂度分析最坏情况 O(√N)但当 N 是质数时需要遍历到 √N。可以使用更高效的 Pollard-Rho 算法处理大整数但试除法在 OJ 中对于N ≤ 10^12通常是够用的。5. 经典 OJ 题实战“投喂”5.1 题目一求正约数个数 (Luogu P1403)问题描述定义 f(n) 为 n 的正约数个数。给定 n求∑_{i1}^{n} f(i)。解题思路直接对每个 i 分解求约数个数会超时。利用算数基本定理的推论我们可以在筛法的过程中递推求出每个数的约数个数。#include iostream #include vector using namespace std; int main() { int n; cin n; long long ans 0; // 对于每个数 i在 1~n 范围内有 n/i 个数包含 i 这个约数 for (int i 1; i n; i) { ans n / i; } cout ans endl; return 0; }5.2 题目二最大公约数之和 (Luogu P1390)问题描述给定 n求∑_{i1}^{n} ∑_{ji1}^{n} gcd(i, j)。解题思路利用欧拉函数 φ 的性质进行转化。设d gcd(i, j)则满足gcd(i, j) d的 (i, j) 对数为2 * ∑_{k2}^{n/d} φ(k) - 1(当 i j)。预处理欧拉函数后求和。#include iostream #include vector using namespace std; vectorint eulerSieve(int n) { vectorint phi(n 1); vectorint primes; vectorbool isPrime(n 1, true); phi[1] 1; for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { if (i * p n) break; isPrime[i * p] false; if (i % p 0) { phi[i * p] phi[i] * p; break; } else { phi[i * p] phi[i] * (p - 1); } } } return phi; } int main() { int n; cin n; vectorint phi eulerSieve(n); long long ans 0; for (int d 1; d n; d) { long long cnt 0; for (int k 2; k n / d; k) { cnt phi[k]; } cnt cnt * 2 1; // 加上 (d, d) 这一对 ans cnt * d; } // 减去所有 (i, i) 的情况因为题目要求 i j for (int i 1; i n; i) { ans - i; } cout ans / 2 endl; // 因为我们计算了 (i, j) 和 (j, i)需要除以2 return 0; }5.3 题目三质因数分解NOIP 2012 普及组问题描述给定正整数 n将其质因数分解按格式输出。解题思路直接使用第 4 节的质因数分解算法即可注意输出格式。6. 总结与进阶算数基本定理是数论大厦的基石。通过本文的“流食般投喂”你应该已经掌握了定理本身及其唯一分解的含义。由定理推导出的核心公式约数个数、约数和。C 实现质因数分解的试除法。如何运用定理解决三类经典 OJ 问题。进阶学习方向更高效的分解算法学习 Pollard-Rho 算法应对更大的整数。线性筛法用欧拉筛在线性时间内预处理出每个数的最小质因数从而实现 O(log N) 的质因数分解。结合其他数论知识将算数基本定理与欧拉定理、中国剩余定理、原根等知识结合解决更复杂的组合数学与密码学问题。理论是灰色的实践之树常青。打开你的 IDE把上面的代码敲一遍再去 OJ 上提交验证这才是“吃透”的唯一路径。