题目信息
- 平台:牛客
- 题目:矩阵游戏
- 难度:简单
- 题目链接:矩形游戏_牛客题霸_牛客网
题目描述
开始时有
然后收回其中一整行石子,手中的石子数变为
当石子数变为
游戏得分为:
请计算最优策略下的最大得分。
输入描述
输入一个整数
输出描述
输出一个整数,表示最大得分。
初步思路
每次操作本质上是选择当前数的一个真因子作为下一个状态。我们希望:
- 尽可能保留较大的中间状态;
- 同时尽可能增加操作次数,让更多状态参与求和。
例如
- 直接选择
: ,得分为 ; - 选择
: ,得分为 。
因此,不能简单地选择最小因子作为下一个状态,而要从整体序列的角度考虑。
关键结论一:每次最好只除以一个质因数
假设某一步从
相比直接跳过去,拆分后额外增加了一个正数状态
所以最优方案中,每次操作都应该只除以一个质数。也就是说,如果:
那么最优过程应该依次除掉这些质因数,最终得到
关键结论二:质因数应该从小到大使用
考虑两个相邻的质因数
如果先除以
如果先除以
两种方案的差别只有中间状态:
- 先除以
,中间得到 ; - 先除以
,中间得到 。
为了让中间状态更大,应当让
因此,质因数应当按照从小到大的顺序依次除掉。
这也等价于:每次寻找当前数的最小质因子并除掉它。
算法流程
- 将答案初始化为
,因为初始状态也计入得分。 - 从
开始试除当前的 。 - 如果
是当前 的因子: - 执行
n /= i; - 将新的
加入答案; - 继续使用同一个
,因为最小质因子可能出现多次。
- 执行
- 如果
不是因子,则令 。 - 循环结束后,如果剩余的
,它一定是一个质数,最后还需要执行一次 ,因此答案加 。
样例:
依次除以最小质因数:
得分为:
样例:
依次除以
得分为:
算法分析
- 核心:质因数分解 + 贪心;
- 贪心策略:每次除以当前数的最小质因子;
- 时间复杂度:
; - 空间复杂度:
。
由于
代码实现
以下给出 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;
}import sys
def solve():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
idx = 1
for _ in range(t):
n = int(data[idx]); idx += 1
ans = n
factor = 2
while factor * factor <= n:
if n % factor == 0:
n //= factor
ans += n
else:
factor += 1
if n > 1:
ans += 1
out.append(str(ans))
sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
solve()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
long n = Long.parseLong(br.readLine().trim());
long ans = n;
for (long factor = 2; factor * factor <= n; ) {
if (n % factor == 0) {
n /= factor;
ans += n;
} else {
++factor;
}
}
if (n > 1) {
ans += 1;
}
sb.append(ans).append('\n');
}
System.out.print(sb);
}
}package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
line, _ := in.ReadString('\n')
line = strings.TrimSpace(line)
t, _ := strconv.Atoi(line)
for i := 0; i < t; i++ {
line, _ = in.ReadString('\n')
line = strings.TrimSpace(line)
n, _ := strconv.ParseInt(line, 10, 64)
ans := n
for factor := int64(2); factor*factor <= n; {
if n%factor == 0 {
n /= factor
ans += n
} else {
factor++
}
}
if n > 1 {
ans += 1
}
fmt.Fprintln(out, ans)
}
}use std::io::{self, BufRead, Write};
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let mut out = io::stdout().lock();
let t: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
for _ in 0..t {
let n: i64 = lines.next().unwrap().unwrap().trim().parse().unwrap();
let mut n = n;
let mut ans = n;
let mut factor = 2i64;
while factor * factor <= n {
if n % factor == 0 {
n /= factor;
ans += n;
} else {
factor += 1;
}
}
if n > 1 {
ans += 1;
}
writeln!(out, "{}", ans).unwrap();
}
}易错点
- 不能只进行一次质因数试除:例如
需要连续除以 三次。 - 因子命中后不能立即递增:当前质因数可能重复出现,应该继续使用同一个因子。
- **剩余的大于
的数需要额外加 **:循环结束时剩余数一定是质数,最后还要从它变成 。 - **答案使用
long long**:虽然,但整个得分由多个状态累加,使用 64 位整数更稳妥。 factor * factor <= n是动态条件:每次除法后变小,循环上界也会随之缩小。
可改进点
- 当
更大(例如 或 )时, 试除可能过慢,可以先做一步 Pollard-Rho 质因数分解,再按相同贪心策略处理。 - 输入若只有单组数据,五种语言的
t处理都可以简化。 - 如果
是质数,答案就是 ,可以特判减少一次循环。
总结
本题看起来是在因数之间进行选择,实际上可以通过两个结论直接确定最优策略:
- 复合因数拆成多个质因数逐步处理,可以增加中间状态,因此更优;
- 相邻质因数中,较小的质因数应该先被除掉,这样中间状态更大。
所以只需要不断除以当前数的最小质因子,并把每次得到的新数累加到答案中即可。