题目信息


题目描述

开始时有 颗石子。每次操作需要选择正整数 ,满足:

然后收回其中一整行石子,手中的石子数变为 。也就是说,每次操作都可以把当前数字变成它的一个真因子。

当石子数变为 时游戏结束。设操作过程中的状态为:

游戏得分为:

请计算最优策略下的最大得分。

输入描述

输入一个整数 :

输出描述

输出一个整数,表示最大得分。


初步思路

每次操作本质上是选择当前数的一个真因子作为下一个状态。我们希望:

  1. 尽可能保留较大的中间状态;
  2. 同时尽可能增加操作次数,让更多状态参与求和。

例如 :

  • 直接选择 :,得分为 ;
  • 选择 :,得分为 。

因此,不能简单地选择最小因子作为下一个状态,而要从整体序列的角度考虑。


关键结论一:每次最好只除以一个质因数

假设某一步从 直接变成 ,其中 。我们可以把它拆成两步:

相比直接跳过去,拆分后额外增加了一个正数状态 ,因此总得分一定更大。

所以最优方案中,每次操作都应该只除以一个质数。也就是说,如果:

那么最优过程应该依次除掉这些质因数,最终得到 。


关键结论二:质因数应该从小到大使用

考虑两个相邻的质因数 ,当前剩余部分为 。

如果先除以 ,状态会经过:

如果先除以 ,状态会经过:

两种方案的差别只有中间状态:

  • 先除以 ,中间得到 ;
  • 先除以 ,中间得到 。

为了让中间状态更大,应当让 更大,也就是先除以较小的质因数 。

因此,质因数应当按照从小到大的顺序依次除掉。

这也等价于:每次寻找当前数的最小质因子并除掉它。


算法流程

  1. 将答案初始化为 ,因为初始状态也计入得分。
  2. 从 开始试除当前的 。
  3. 如果 是当前 的因子:
    • 执行 n /= i;
    • 将新的 加入答案;
    • 继续使用同一个 ,因为最小质因子可能出现多次。
  4. 如果 不是因子,则令 。
  5. 循环结束后,如果剩余的 ,它一定是一个质数,最后还需要执行一次 ,因此答案加 。

样例:

依次除以最小质因数:

得分为:

样例:

依次除以 :

得分为:


算法分析

  • 核心:质因数分解 + 贪心;
  • 贪心策略:每次除以当前数的最小质因子;
  • 时间复杂度:;
  • 空间复杂度:。

由于 ,试除到 的复杂度可以满足要求。


代码实现

以下给出 C++、Python、Java、Go、Rust 五种语言的实现,逻辑完全一致。切换上方的标签即可对比。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    long long answer = n;

    for (long long factor = 2; factor * factor <= n; ) {
        if (n % factor == 0) {
            n /= factor;
            answer += n;
        } else {
            ++factor;
        }
    }

    if (n > 1) {
        answer += 1;
    }

    cout << answer << '\n';

    return 0;
}

易错点

  1. 不能只进行一次质因数试除:例如 需要连续除以 三次。
  2. 因子命中后不能立即递增:当前质因数可能重复出现,应该继续使用同一个因子。
  3. **剩余的大于 的数需要额外加 **:循环结束时剩余数一定是质数,最后还要从它变成 。
  4. **答案使用 long long**:虽然 ,但整个得分由多个状态累加,使用 64 位整数更稳妥。
  5. factor * factor <= n 是动态条件:每次除法后 变小,循环上界也会随之缩小。

可改进点

  • 当 更大(例如 或 )时, 试除可能过慢,可以先做一步 Pollard-Rho 质因数分解,再按相同贪心策略处理。
  • 输入若只有单组数据,五种语言的 t 处理都可以简化。
  • 如果 是质数,答案就是 ,可以特判减少一次循环。

总结

本题看起来是在因数之间进行选择,实际上可以通过两个结论直接确定最优策略:

  1. 复合因数拆成多个质因数逐步处理,可以增加中间状态,因此更优;
  2. 相邻质因数中,较小的质因数应该先被除掉,这样中间状态更大。

所以只需要不断除以当前数的最小质因子,并把每次得到的新数累加到答案中即可。