CF177B2 Rectangular Game 题解

题意简述


似乎与这道题一样啊。

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

解题思路


首先这是一道贪心

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

但是显然,如果 xx11,答案就为 nn,显然无法取到最优解,所以我们要稍加改变。

读题可知 xZ,yZx \in \mathbb{Z} , y \in \mathbb{Z}x1x \neq 1,这样就是在求 nn 除一以外的最小约数。递归即可。

这里有几点要注意一下:

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

  2. 最后要将 ans+1ans + 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