题目翻译
给定一个 n n n,寻找一个 x x x 使得:
- 2 ≤ x ≤ n 2\le x\le n 2≤x≤n。
- 所有小于等于 n n n 的 x x x 的倍数的和最大。
输出这个 x x x。
本题每个样例有 t t t 组测试数据。
思路
对于这道题,可以枚举 x x x 的值,找到符合要求的 x x x。
显然,对于每一个
x
x
x 直接暴力累加倍数和会 TLE。可以发现,对于任意一个数,它的倍数是一个等差数列,故可以用高斯求和法求和。所以可以得到,对于任意一个
x
x
x,所有小于等于
n
n
n 的
x
x
x 的倍数的和为:
(
x
+
n
−
n
m
o
d
x
)
×
(
n
−
n
m
o
d
x
−
x
x
+
1
)
2
\frac{(x+n-n\bmod x)\times(\frac{n-n\bmod x-x}{x}+1)}{2}
2(x+n−nmodx)×(xn−nmodx−x+1)
Code
#include<iostream>
using namespace std;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n,ans,x,ma;
cin>>t;
while(t--) {
cin>>n,ma=0;
for(x=2;x<=n;++x) {//枚举x的值
int sum=(x+n-n%x)*((n-n%x-x)/x+1)/2;//套入公式,int会自动向下取整
if(sum>ma) ans=x,ma=sum;//比较大小
}
cout<<ans<<"\n";//输出答案,记得换行
}
return 0;
}