矩形游戏
时间限制：1 秒
空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
旺仔哥哥设计了一种"石子矩形"游戏。游戏开始时，旺仔哥哥拥有n nn颗石子。一次游戏操作的流程如下：
- 选择一对正整数( a , b ) (a, b)(a,b)，满足a > 1 a > 1a>1且n = a × b n = a \times bn=a×b；
- 将全部石子摆放成a aa行，每行恰好b bb颗；
- 收回任意一整行石子（共b bb颗），其余石子全部丢弃。
一次操作结束后，旺仔哥哥手中的石子数变为b bb。随后，旺仔哥哥可在新的石子数上继续进行同样的操作；当且仅当手中仅剩1 11颗石子时，游戏才会停止。
设旺仔哥哥在第i ii轮操作结束时手中的石子数为c i c_ici，整个过程满足
- c 1 = n c_1 = nc1=n；
- c i + 1 c_{i+1}ci+1是c i c_ici的一个真因子，且c i + 1 < c i c_{i+1} < c_ici+1<ci；
- 存在最小的整数k kk使得c k = 1 c_k = 1ck=1。
游戏得分定义为
∑ i = 1 k c i \sum_{i=1}^{k} c_ii=1∑kci
现给定初始石子数n nn，请计算旺仔哥哥在最优策略下可以获得的最大得分。
输入描述
在一行上输入一个整数n ( 2 ≤ n ≤ 10 9 ) n\ (2 \le n \le 10^9)n(2≤n≤109)，表示旺仔哥哥最开始拥有的石子数量。
输出描述
在一行上输出一个整数，表示旺仔哥哥能够获得的最大得分。
示例 1
输入：
10输出：
16说明：在该样例中，最优操作序列为
- 第1 11轮：10 = 2 × 5 10 = 2 \times 510=2×5，收回5 55颗，得到c 2 = 5 c_2 = 5c2=5；
- 第2 22轮：5 = 5 × 1 5 = 5 \times 15=5×1，收回1 11颗，得到c 3 = 1 c_3 = 1c3=1。
最终得分= 10 + 5 + 1 = 16 = 10 + 5 + 1 = 16=10+5+1=16。
示例 2
输入：
8输出：
15说明：在该样例中，最优操作序列为
- 第1 11轮：8 = 2 × 4 8 = 2 \times 48=2×4，收回4 44颗，得到c 2 = 4 c_2 = 4c2=4；
- 第2 22轮：4 = 2 × 2 4 = 2 \times 24=2×2，收回2 22颗，得到c 3 = 2 c_3 = 2c3=2；
- 第3 33轮：2 = 2 × 1 2 = 2 \times 12=2×1，收回1 11颗，得到c 4 = 1 c_4 = 1c4=1。
最终得分= 8 + 4 + 2 + 1 = 15 = 8 + 4 + 2 + 1 = 15=8+4+2+1=15。
数据范围
- 2 ≤ n ≤ 10 9 2 \le n \le 10^92≤n≤109
解题思路
本题是贪心 + 质因数分解的数学问题。给定初始石子数n nn，每次操作可以将当前数n nn分解为n = a × b n = a \times bn=a×b（a > 1 a>1a>1），然后保留b bb颗石子（即丢弃a − 1 a-1a−1行），下一轮从b bb继续。游戏直到只剩 1 颗石子停止。得分是每轮结束后的石子数之和（包括初始的n nn和最后的 1）。要求最大化总得分。
1. 问题等价转化
- 每次操作本质上是将当前数c cc除以它的一个因子a aa（a > 1 a>1a>1），得到b = c / a b = c/ab=c/a，且b < c b < cb<c。得分累加b bb。
- 目标：选择一系列因子，使得从n nn逐步除到 1 的过程中，每一步得到的商之和最大。
- 由于每一步的得分是除法后的商，为了让总和最大，我们希望每次除法后的商尽可能大。也就是说，每次选择的因子a aa应该尽可能小（因为b = c / a b = c/ab=c/a，a aa越小，b bb越大）。
- 最小的可行因子a aa是当前数c cc的最小质因数（若c cc为质数，则只能选a = c a=ca=c，得到b = 1 b=1b=1）。
- 因此，最优策略是：每次用当前数的最小质因数去除，直到变为 1。这样得到的序列就是n nn依次除以它的最小质因数，直到 1。
2. 算法实现
代码采用贪心模拟：
- 读入n nn，初始化答案
ans = n（初始石子数计入得分）。 - 从i = 2 i = 2i=2开始枚举因子，直到i × i > n i \times i > ni×i>n：
- 若n nn能被i ii整除，说明i ii是当前n nn的一个因子（实际上是最小质因数，因为从小到大枚举）。
- 执行除法：
n /= i，将新的n nn累加到ans中。 - 将
i重置为 1（循环末尾i++后变为 2），重新从最小的因子开始检查新的n nn。这是因为除以i ii后，新的n nn可能仍然能被i ii整除，或者有更小的质因数（但之前已经检查过更小的，所以重置为 1 是安全的且能继续分解）。
- 循环结束后，若n > 1 n > 1n>1，说明n nn本身是一个质数，最后一步只能除以n nn得到 1。将 1 加入答案（代码中直接输出
ans + 1）。 - 输出总得分。
注意：代码中的i = 1是为了在for循环的i++后从 2 重新开始，确保每次都用当前数的最小质因数去除。由于n nn每次至少除以 2，循环次数为O ( log n ) O(\log n)O(logn)，非常快。
3. 复杂度分析
- 时间复杂度：每次除法后n nn至少减半，且因子枚举从 2 开始，最坏情况（n nn为质数）只需枚举到n \sqrt{n}n。总操作次数约为O ( n ) O(\sqrt{n})O(n)加上除法次数，对于n ≤ 10 9 n \le 10^9n≤109，n ≈ 31623 \sqrt{n} \approx 31623n≈31623，完全可行。
- 空间复杂度：仅使用常数个变量，O ( 1 ) O(1)O(1)。
总结
通过分析可知，为了最大化得分，每次应选择当前数的最小质因数进行除法，使得得到的商尽可能大。代码通过从小到大枚举因子并重置枚举起点，实现了这一贪心策略，最终累加所有商和最后的 1 即为答案。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;ll ans=n;for(ll i=2;i*i<=n;i++){if(n%i==0){n/=i;ans+=n;i=1;}}cout<<ans+1;return0;}
