题解 | #矩形游戏#

题目链接

题目描述

从 $N$ 颗石子开始，每次操作可以选择将当前的 $N$ 颗石子摆成 $r \cdot c$ 的矩形（其中 $r>1$ ），然后保留其中一行的 $c$ 颗石子，其余丢弃。游戏在剩下 1 颗石子时结束。游戏得分是每轮操作前所拥有的石子数之和。求最优策略下的最大得分。

解题思路

本题要求一个最大得分，这是一个典型的最优化问题，我们可以尝试用动态规划的思路来分析。

设 $f(n)$ 表示从 $n$ 颗石子开始游戏能获得的最大得分。根据题意，游戏在剩下 1 颗石子时结束，所以 $f(1) = 1$ 。对于 $n > 1$ 的情况，一次操作将石子数从 $n$ 变为 $c$ ，其中 $c$ 是 $n$ 的一个真因子（ $c < n$ ）。得分会增加 $n$ ，之后的游戏得分则取决于从 $c$ 开始能获得的最大分数 $f(c)$ 。为了使总分最大，我们应该选择一个能使后续得分 $f(c)$ 最大的真因子 $c$ 。因此，我们可以写出状态转移方程： $f(n) = n + \max_{c|n, c<n} \{f(c)\}$

接下来我们分析 $f(n)$ 函数的性质。 $f(n)$ 是一个严格单调递增的函数。也就是说，如果 $n_1 > n_2$ ，那么 $f(n_1) > f(n_2)$ 。这是因为 $f(n) = n + \dots$ 至少等于 $n+1$ ，所以 $n_1 > n_2$ 保证了 $f(n_1)$ 的首项就大于 $f(n_2)$ 的首项，后续的累加项也遵循这个规律，因此总和也更大。

既然 $f(c)$ 随着 $c$ 的增大而增大，那么为了让 $\max\{f(c)\}$ 最大，我们应该选择最大的那个真因子 $c$ 。一个数 $n$ 的最大真因子可以通过用 $n$ 除以它的最小质因子得到。例如， $10$ 的最小质因子是 $2$ ，其最大真因子就是 $10/2=5$ 。 $8$ 的最小质因子是 $2$ ，其最大真因子是 $8/2=4$ 。

因此，最优策略在每一步都是确定的：从当前的石子数 $n$ 变成它的最大真因子。

算法流程如下：

初始化总得分 score 为 0，当前石子数 current_n 为 $N$ 。
进入一个循环，只要 current_n 大于 0： a. 将 current_n 加入到 score 中。 b. 如果 current_n 等于 1，游戏结束，跳出循环。 c. 找到 current_n 的最小质因子 $p$ 。 d. 更新 current_n 为它的最大真因子，即 current_n / p。
返回 score。

寻找最小质因子可以通过试除法实现：从 2 开始向上遍历，第一个能整除 current_n 的数就是它的最小质因子。

代码

c++
java
python

#include <iostream>

using namespace std;

// 查找n的最小质因子
long long find_smallest_prime_factor(long long n) {
    if (n % 2 == 0) {
        return 2;
    }
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return i;
        }
    }
    // 如果没有找到小于等于其平方根的因子，说明n本身是质数
    return n;
}

int main() {
    long long n;
    cin >> n;
    long long score = 0;
    while (n > 0) {
        score += n;
        if (n == 1) {
            break;
        }
        long long p = find_smallest_prime_factor(n);
        n /= p;
    }
    cout << score << "\n";
    return 0;
}

import java.util.Scanner;

public class Main {
    // 查找n的最小质因子
    public static long findSmallestPrimeFactor(long n) {
        if (n % 2 == 0) {
            return 2;
        }
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return i;
            }
        }
        // 如果没有找到小于等于其平方根的因子，说明n本身是质数
        return n;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long score = 0;
        
        while (n > 0) {
            score += n;
            if (n == 1) {
                break;
            }
            long p = findSmallestPrimeFactor(n);
            n /= p;
        }
        System.out.println(score);
    }
}

def find_smallest_prime_factor(n):
    """查找n的最小质因子"""
    if n % 2 == 0:
        return 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return i
        i += 2
    # 如果没有找到小于等于其平方根的因子，说明n本身是质数
    return n

n = int(input())
score = 0
while n > 0:
    score += n
    if n == 1:
        break
    p = find_smallest_prime_factor(n)
    n //= p

print(score)

算法及复杂度

算法：贪心算法 + 试除法
时间复杂度： $O(\sqrt{N})$ 。游戏进行的步数是 $N$ 的质因子个数，为 $O(\log N)$ 级别。每一步都需要寻找最小质因子，这需要 $O(\sqrt{N_i})$ 的时间，其中 $N_i$ 是当前步的石子数。整个过程的总时间由第一步寻找最小质因子的时间决定，即 $O(\sqrt{N})$ 。
空间复杂度： $O(1)$ ，只需要常数个变量。