题目大意
定义 \(\text{MSLCM}(n)\) 为所有满足该数集的 \(\text{lcm}\) 为 \(n\) 的数集中元素个数最多的数集的所有数字的和，现有多次询问，求
\[\sum_{i=2}^n\text{MSLCM}(i) \]思路分析
大水题。
虽然看着这个东西很可怕，但仔细一想你就会发现，其实 \(\text{MSLCM}(n)=\sum_{d|n}d\)，这个所谓的数集其实就是由 \(n\) 的约数集，因为只有这样才能满足元素个数最多的条件。
那么我们要求的就是下面这个
\[\sum_{i=2}^n\sum_{d|i}d \]简单化一下
\[\begin{aligned}&\sum_{i=2}^n\sum_{d|i}d\\&=\sum_{i=1}^n\sum_{d|i}d-1\\&=\sum_{i=1}^n\sum_{d=1}^nd[d|i]-1\\&=\sum_{d=1}^nd\sum_{i=1}^n[d|i]-1\\&=\sum_{d=1}^nd\lfloor\frac{n}{d}\rfloor-1\end{aligned} \]只需要整除分块就好了。
时间复杂度：\(O(T\sqrt n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long//好习惯
int n,ans;
signed main(){
while(true){
scanf("%lld",&n);
if(n==0) return 0;ans=0;
for(int l=1,r;l<=n;l=r+1){//整除分块
r=n/(n/l);
ans+=(n/l)*(r+l)*(r-l+1)/2;
}
cout<<ans-1<<'\n';
}
return 0;
}