\(Decription:\)
给出两个数n,k，求\(\sum_{i=1}^{n}k\%i\)
\(Sample\) \(Input:\)
10 5
\(Sample\) \(Output:\)
29
这题要求余数的和，考虑和除法有些密不可分的关系，那就化化式子
\(\sum_{i=1}^{k} k-k/i*i\)
\(n*k-\sum_{i=1}^{k} k/i*i\)
那么我们考虑用除法分块求。
每一个块内的和是等差数列，那么可以快速就出一个块的和。
因为块的个数不会对于根号个，所以复杂度有保证。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,ans,l,r;
signed main(){
scanf("%lld%lld",&n,&k);
for(l=1;l<=n;l=r+1){
if(k/l!=0) r=min(k/(k/l),n);
else r=n;
ans-=(k/l)*(r-l+1)*(l+r)>>1;
}
ans+=n*k;
printf("%lld\n",ans);
return 0;
}