CF177B2 Rectangular Game 题解

题意简述

似乎与这道题一样啊。

给定一个整数 $n$,请构造一个 $x \times y$ 的矩形，每次只留下最上面一行，并将最上面一行的个数累加进 $ans$。求 $ans$ 的值。

解题思路

首先这是一道贪心。

我们要让总和最大，就是要让第一行最大。

但是显然，如果 $x$ 为 $1$，答案就为 $n$，显然无法取到最优解，所以我们要稍加改变。

读题可知 $x \in \mathbb{Z} , y \in \mathbb{Z}$ 且 $x \neq 1$，这样就是在求 $n$ 除一以外的最小约数。递归即可。

这里有几点要注意一下：

1. $n$ 可能是个素数，而我们枚举最小约数是到 $\sqrt{n}$。所以在这种情况下只能使 $x = 1$。

2. 最后要将 $ans + 1$，因为最后肯定还剩下一个。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main() {
	scanf("%d",&n);
	while(n>=1) {
		bool flag=false;
		for(int i=2;i<=sqrt(n);i++) {
			if(n%i==0) {
				ans+=n; n/=i;
				flag=true; break;
			}
		}
		if(!flag) { ans+=n; break;}
	}
	printf("%d",ans+1);
	return 0;
}
//code by TheCedar