BISHI58　矩形游戏¶

简单通过率 51.71%python3样例通过牛客 AC

讲解章节：数论基础

一句话

每轮把 n 换成它的一个真因子，直到 1，最大化经过的数之和。

解题思路¶

这题考什么¶

质因数分解 + 贪心。一次操作把 c 变成 c 的某个真因子 c/p（p 是 c 的某个 > 1 的因子）。把整条链写出来：n, n/d1, n/(d1 d2), ..., 1，其中 d1d2...dk = n 且每个 di > 1。要让所有前缀商之和最大，就要让每个前缀积 d1...dj 尽可能小；而 d 的乘积固定为 n，所以最优是把 n 的质因子从小到大*逐个除掉（拆得越碎、越先除小的，每一步的前缀积越小，链也越长）。

于是答案 = n + n/p1 + n/(p1 p2) + ... + 1，其中 p1 <= p2 <= ... <= pk 是 n 的全部质因子（按重数）升序。

数据规模与复杂度¶

n <= 1e9 → 试除到 sqrt(n) <= 31623，O(sqrt n)，一组数据毫秒级。质因子个数不超过 30（2^30 > 1e9），链长很短。

坑在哪¶

a > 1 保证了每轮必须真的变小，所以链一定能走到 1，且 1 也计入得分（样例 10 -> 10+5+1 = 16 就包含末尾的 1）；
要按重数展开，比如 8 = 222，链是 8,4,2,1 而不是 8,1；
用 math.isqrt 而不是 n ** 0.5；这里写成 d*d <= n 同样安全；
答案最大约为 2n（等比和 n + n/2 + n/4 + ... < 2n），不会溢出；
n 本身是质数时链只有 n -> 1，答案 n + 1，靠「循环结束后 m > 1 补一个」这一步兜住，漏了它会输出 n 而少算 1。

样例复核¶

n = 10：质因子升序是 [2, 5]，链为 10 -> 5 -> 1，得分 10 + 5 + 1 = 16 ✓（先除 2 而不是先除 5，才留下更大的中间项 5）。 n = 8：质因子是 [2, 2, 2]，链为 8 -> 4 -> 2 -> 1，得分 15 ✓。

质因数分解见 80-数论基础。

参考实现¶

solutions/BISHI58.py
import sys


def main() -> None:
    n = int(sys.stdin.buffer.read().split()[0])
    primes = []                      # 按重数展开的质因子，天然升序
    m = n                            # 用副本分解，n 本身后面还要当链的起点
    d = 2
    while d * d <= m:                # 上界随 m 缩小自动收紧
        while m % d == 0:
            primes.append(d)         # 除几次记几次，重数决定链有多长
            m //= d
        d += 1 if d == 2 else 2      # 2 -> 3，之后只试奇数
    if m > 1:                        # 剩下的是唯一那个大于 sqrt 的质因子
        primes.append(m)

    cur = n
    ans = n                          # c_1 = n 本身也计入得分
    for p in primes:                 # 升序除，每步商最大
        cur //= p
        ans += cur                   # 最后一次除完 cur 恰好是 1，末尾的 1 自动含入
    sys.stdout.write(str(ans) + "\n")


main()

BISHI58 矩形游戏¶