洛谷 CF1985B Maximum Multiple Sum 题解

本文主要是介绍洛谷 CF1985B Maximum Multiple Sum 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目翻译

给定一个 $n$，寻找一个 $x$ 使得：

• $2\le x\le n$。
• 所有小于等于 $n$ 的 $x$ 的倍数的和最大。

输出这个 $x$。

本题每个样例有 $t$ 组测试数据。

思路

对于这道题，可以枚举 $x$ 的值，找到符合要求的 $x$。

显然，对于每一个 $x$ 直接暴力累加倍数和会 TLE。可以发现，对于任意一个数，它的倍数是一个等差数列，故可以用高斯求和法求和。所以可以得到，对于任意一个 $x$，所有小于等于 $n$ 的 $x$ 的倍数的和为：
$$\frac{(x+n-n\mathrm{mod}x)\times (\frac{n-n\mathrm{mod}x-x}{x}+1)}{2}$$

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;
}

这篇关于洛谷 CF1985B Maximum Multiple Sum 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---