求解 1 到 N 与 N 的最大公约数之和：从数学推导到 C++ 实现

已知： \[ S(N) = \sum_{k=1}^N \gcd(k, N) \] 要求 \(1 \le N \le 2^{31}-1\)。 --- ## 1. 推导公式 设 \(d\) 是 \(N\) 的约数，即 \(d \mid N\)。 \(\gcd(k, N) = d\) 当且仅当 \(\gcd\left(\frac{k}{d}, \frac{N}{d}\right) = 1\)，且 \(1 \le k \le N\)。 满足条件的 \(k\) 的个数为 \(\varphi\left(\frac{N}{d}\right)\)，其中 \(\varphi\) 是欧拉函数。 因此： \[ \sum_{k=1}^N \gcd(k, N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 或者等价地（令 \(d' = \frac{N}{d}\)）： \[ \sum_{d \mid N} \varphi(d) \cdot \frac{N}{d} \] --- ## 2. 更简洁的形式 已知数论恒等式： \[ \sum_{k=1}^N \gcd(k, N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 也可以写成： \[ \sum_{d \mid N} \varphi(d) \cdot \frac{N}{d} \] 但更常用的是： \[ \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 因为计算时枚举 \(N\) 的约数 \(d\)，直接求 \(\varphi(N/d)\) 即可。 --- ## 3. 算法步骤 1. 对 \(N\) 分解质因数。 2. 枚举 \(N\) 的所有约数 \(d\)（通过质因数组合）。 3. 对每个 \(d\)，计算 \(\varphi\left(\frac{N}{d}\right)\)。 4. 累加 \(d \cdot \varphi\left(\frac{N}{d}\right)\)。 --- ## 4. 时间复杂度 \(N\) 最多约 \(2.1 \times 10^9\)，约数个数最多约 \(1536\) 个（实际更少）。 分解质因数用试除到 \(\sqrt{N}\) 即可（\(\sqrt{N} \approx 46340\)），可以接受。 枚举约数并计算欧拉函数是可行的。 --- ## 5. 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; // 分解质因数 vector<pair<long long, int>> factorize(long long n) { vector<pair<long long, int>> factors; for (long long p = 2; p * p <= n; p++) { if (n % p == 0) { int cnt = 0; while (n % p == 0) { n /= p; cnt++; } factors.emplace_back(p, cnt); } } if (n > 1) { factors.emplace_back(n, 1); } return factors; } // 通过质因数计算欧拉函数 long long euler_phi(long long n, const vector<pair<long long, int>>& factors) { long long res = n; for (auto& [p, _] : factors) { if (n % p == 0) { res -= res / p; } } return res; } // 生成所有约数 void generate_divisors(int idx, long long cur, const vector<pair<long long, int>>& factors, vector<long long>& divisors) { if (idx == factors.size()) { divisors.push_back(cur); return; } long long p = factors[idx].first; int exp = factors[idx].second; long long pow = 1; for (int i = 0; i <= exp; i++) { generate_divisors(idx + 1, cur * pow, factors, divisors); pow *= p; } } int main() { long long N; cin >> N; // 分解 N 的质因数 auto factors = factorize(N); // 生成 N 的所有约数 vector<long long> divisors; generate_divisors(0, 1, factors, divisors); // 计算 S(N) = sum_{d|N} d * phi(N/d) long long ans = 0; for (long long d : divisors) { long long m = N / d; // 计算 phi(m)，需要 m 的质因数分解 // 但 m 的质因数一定是 N 的质因数的子集 // 所以可以从 factors 中筛选出整除 m 的质因数 vector<pair<long long, int>> m_factors; long long tmp = m; for (auto& [p, exp] : factors) { if (tmp % p == 0) { int cnt = 0; while (tmp % p == 0) { tmp /= p; cnt++; } m_factors.emplace_back(p, cnt); } } if (tmp > 1) { m_factors.emplace_back(tmp, 1); } long long phi_m = euler_phi(m, m_factors); ans += d * phi_m; } cout << ans << endl; return 0; } ``` --- ## 6. 样例验证 输入： ``` 6 ``` 约数：1, 2, 3, 6 计算： - d=1, N/d=6, φ(6)=2 → 贡献 1×2=2 - d=2, N/d=3, φ(3)=2 → 贡献 2×2=4 - d=3, N/d=2, φ(2)=1 → 贡献 3×1=3 - d=6, N/d=1, φ(1)=1 → 贡献 6×1=6 总和：2+4+3+6=15 ✅ --- 最终公式： \[ S(N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 用上述代码可在 \(O(\sqrt{N} + \tau(N)^2)\) 时间内完成，其中 \(\tau(N)\) 是 \(N\) 的约数个数。 ######[AI问答 | 1434点数解答 | 2026-01-20 14:05:17]