整数分解难题：求最小公倍数为 n 时的最小整数和

问题分析 给定整数 \( n \)，要求找到至少两个正整数，它们的最小公倍数为 \( n \)，且这些数的和最小。输出最小的和。 关键思路 1. 若 \( n \) 是质数或质数的幂，则至少需要两个数，最小和为 \( n + 1 \)（例如 \( n \) 和 1 的最小公倍数为 \( n \)，但 1 不能重复使用，所以用 \( n \) 和 1 不满足“至少两个正整数”吗？注意：1 是正整数，但 1 和 n 的最小公倍数是 n，且 1 + n = n+1。 但更优分解：若 \( n = p^k \)（p 是质数），可分解为 \( p^{k-1} \) 和 \( p \)，最小公倍数为 \( p^k = n \)，和为 \( p^{k-1} + p \)，这比 \( n+1 \) 小吗？ 检验：\( p^{k-1} + p \) 与 \( p^k + 1 \) 比较。 例如 \( p=2, k=3, n=8 \)： - 分解为 4 和 2：和=6 - 分解为 8 和 1：和=9 所以更优。 2. 一般情况： 设 \( n = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m} \)（质因数分解）。 最小公倍数为 n 的条件：每个质因子的幂次最大值等于 \( a_i \)。 要使得总和最小，应尽量让每个数只含部分质因子，避免重复包含多个质因子的高次幂。 最优策略：每个质因子的幂 \( p_i^{a_i} \) 单独作为一个数，这样这些数两两互质，最小公倍数就是乘积 n，且和为 \( \sum p_i^{a_i} \)。 但注意：至少两个数，所以如果 m=1（n 是质数幂），则必须拆成至少两个数，上面已讨论。 3. 特殊情况：n=1 时，至少两个正整数最小公倍数为 1，只能是 1 和 1，和为 2。但题目 n ≥ 1，且 n=1 时？题目 n < 2^31，没说 n>1，但至少两个正整数最小公倍数为 1 只能是 1 和 1，和=2。 算法步骤 1. 对 n 进行质因数分解。 2. 如果只有一个质因子（m=1），即 \( n = p^a \)： - 若 a=1（n 是质数），只能拆成 1 和 n，和 = n+1。 - 若 a>1，最优拆成 \( p^{a-1} \) 和 \( p \)，和 = \( p^{a-1} + p \)。 3. 如果有多个质因子（m≥2），最优和为各个质因子幂的和：\( \sum_{i=1}^m p_i^{a_i} \)。 4. 注意：如果 n=1，质因数分解为空，此时和为 2（1+1）。 验证样例 - n=12 = 2^2 * 3^1 → 质因子幂：4 和 3，和=7。 - n=10 = 2^1 * 5^1 → 质因子幂：2 和 5，和=7。 - n=5 = 5^1（质数）→ 和=5+1=6。 符合样例输出。 代码实现（C++） ```cpp #include <iostream> #include <cmath> using namespace std; long long solve(long long n) { if (n == 1) return 2; long long sum = 0; int cnt = 0; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { cnt++; long long p = 1; while (n % i == 0) { n /= i; p *= i; } sum += p; } } if (n > 1) { // 剩下一个质因子 cnt++; sum += n; } if (cnt == 1) { // n 是质数或质数的幂 // 需要拆成至少两个数 // 如果原数是质数，则只能拆成 1 和 n，和 = n+1 // 如果原数是质数的幂 p^a，最优拆成 p^(a-1) 和 p // 但上面 sum 此时等于 p^a，需要调整： // 例如 n=8=2^3，sum=8，但最优是 4+2=6。 // 所以需要找到质因子 p 和幂次 a // 简便方法：sum 是 p^a，最优和是 p^(a-1) + p // 即 sum / p + p，其中 p 是最小的质因子。 // 但我们已经除尽了，所以需要重新求 p 和 a？可以在循环中记录。 // 这里简化：如果 cnt==1，说明 n 最初是 p^a，现在 n=1，p 和 a 丢失了。 // 所以需要在循环中记录。 // 修改：在循环中记录 p 和 a。 } return sum; } // 修正版本：记录质因子和幂次 long long solve2(long long n) { if (n == 1) return 2; long long sum = 0; int cnt = 0; long long last_p = 1, last_a = 0; long long original_n = n; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { cnt++; long long p = 1; int a = 0; while (n % i == 0) { n /= i; p *= i; a++; } sum += p; if (cnt == 1) { last_p = i; last_a = a; } } } if (n > 1) { cnt++; sum += n; if (cnt == 1) { last_p = n; last_a = 1; } } if (cnt == 1) { // n 原来是 last_p^last_a // 最优拆成 last_p^(last_a-1) 和 last_p long long p = last_p; long long a = last_a; long long best = pow(p, a-1) + p; // 但注意 a=1 时（质数），pow(p,0)=1，和=p+1 return best; } return sum; } int main() { long long n; while (cin >> n && n != 0) { cout << solve2(n) << endl; } return 0; } ``` 说明 - 使用质因数分解，对每个质因子取最高次幂作为一个数。 - 如果只有一个质因子，需要拆成两个数使得和最小。 - 注意 n=1 的特殊情况。 - 多组输入以 0 结束。 ######[AI问答 | 1677点数解答 | 2026-01-11 17:48:52]