BGN48 矩形游戏

思路

题目说的是一个石子游戏：起初有 颗石子，每次操作把石子排成 的矩形（），然后只留下一行（ 颗），其余全丢掉。反复操作直到剩 1 颗，把过程中每次的石子数（包括初始的 和最后的 ）加起来，求最大得分。

说白了，每次操作就是把当前数 替换成它的一个真因子 （因为 ，所以 ）。我们要选择一条从 到 的因子链，使得链上所有数的和最大。

该除以谁？

假设当前是 ，我们要选一个大于 1 的因子 把它除掉，变成 。想让总和尽可能大，那每一步保留的值就要尽可能大 —— 也就是 要尽可能小。 最小能取多少？就是 的最小质因子。

所以最优策略就是：每次都除以当前数的最小质因子。

举例验证

：

$$

得分 。如果反过来先除以 5 再除以 2，得 ，明显更小。

：

$$

得分 。

为什么贪心是对的？

直觉上，每一步除以更小的数，剩下的值更大，后续所有项都在更高的基础上累加。严格来说，假设某一步我们可以除以 （小质因子）或 （大质因子），除以 之后这一步贡献 ，除以 贡献 ，光是这一步就多了 。而后续的操作面对的数更大，也不会更差。所以每步选最小质因子一定是全局最优。

实现

  1. 对 做质因数分解，把所有质因子（带重复）从小到大排好。
  2. 从 出发，依次除以每个质因子，累加每步的值。

质因数分解用试除法， 就够了。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n;
    scanf("%lld", &n);

    vector<long long> factors;
    long long tmp = n;
    for(long long i = 2; i * i <= tmp; i++){
        while(tmp % i == 0){
            factors.push_back(i);
            tmp /= i;
        }
    }
    if(tmp > 1) factors.push_back(tmp);

    long long ans = n;
    long long cur = n;
    for(long long f : factors){
        cur /= f;
        ans += cur;
    }

    printf("%lld\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        List<Long> factors = new ArrayList<>();
        long tmp = n;
        for (long i = 2; i * i <= tmp; i++) {
            while (tmp % i == 0) {
                factors.add(i);
                tmp /= i;
            }
        }
        if (tmp > 1) factors.add(tmp);

        long ans = n;
        long cur = n;
        for (long f : factors) {
            cur /= f;
            ans += cur;
        }

        System.out.println(ans);
    }
}

import sys

def main():
    n = int(sys.stdin.readline())
    factors = []
    tmp = n
    i = 2
    while i * i <= tmp:
        while tmp % i == 0:
            factors.append(i)
            tmp //= i
        i += 1
    if tmp > 1:
        factors.append(tmp)

    ans = n
    cur = n
    for f in factors:
        cur //= f
        ans += cur

    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let n = BigInt(lines[0].trim());
    const factors = [];
    let tmp = n;
    for (let i = 2n; i * i <= tmp; i++) {
        while (tmp % i === 0n) {
            factors.push(i);
            tmp /= i;
        }
    }
    if (tmp > 1n) factors.push(tmp);

    let ans = n;
    let cur = n;
    for (const f of factors) {
        cur /= f;
        ans += cur;
    }
    console.log(ans.toString());
});

复杂度分析

  • 时间复杂度：，瓶颈在试除法分解质因数。
  • 空间复杂度：，存储质因子列表（ 最多有 个质因子）。