C++ 数学-数论：算数基本定理及其经典 OJ 题流食般投喂-育师

1. 引言：为什么需要算数基本定理？

在算法竞赛和编程面试中，数论问题常常是区分选手水平的关键。而算数基本定理（Fundamental Theorem of Arithmetic），作为数论的基石之一，为我们理解和解决一大类整数分解、约数、最大公约数、最小公倍数等问题提供了强大的理论武器。掌握它，就如同掌握了打开数论问题宝库的钥匙。

本文将用“流食般投喂”的方式，从零开始，带你彻底吃透算数基本定理，并辅以多道经典 OJ（Online 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; // 返回一个映射，键为质因数，值为对应的指数 map<int, int> primeFactorization(int n) { map<int, 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 map<int, 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，求∑_{i=1}^{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，求∑_{i=1}^{n} ∑_{j=i+1}^{n} gcd(i, j)。

解题思路：利用欧拉函数 φ 的性质进行转化。设d = gcd(i, j)，则满足gcd(i, j) = d的 (i, j) 对数为2 * ∑_{k=2}^{n/d} φ(k) - 1(当 i < j)。预处理欧拉函数后求和。

#include <iostream> #include <vector> using namespace std; vector<int> eulerSieve(int n) { vector<int> phi(n + 1); vector<int> primes; vector<bool> 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; vector<int> 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; }