P2261 [CQOI2007]余数求和

我是题面

题意还是很清晰，很容易理解

1e9范围明显不能暴力，除非你能把常数优化到(frac1 {10})，但我实在想象不到用了这么多取模怎么把常数优化下去

我们可以把(k\%i)变成(k-k/i*i)(整除)

那么总的和也就从(sum_{i=1}^{n}k\%i)变成了(sum_{i=1}^n k-k/i*i)，又可以转化为(nk-sum_{i=1}^n k/i*i)

(k/i)的值只有有(sqrt k)种，且相同的值都是连续出现的，所以我们可以直接利用等差数列求(sum_{i=1}^n k/i*i)

下面放代码吧

#include
#include
#include
#include
#include
#define ll long long
#define gc getchar
using namespace std;inline ll read(){ll a=0;int f=0;char p=gc();while(!isdigit(p)){f|=p=='-';p=gc();}while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}return f?-a:a;
}ll n,k,ans;int main(){n=read();k=read();for(int l=1,r;l<=n;l=r+1){if(k/l)r=min(k/(k/l),n);else r=n;ans+=k/l*(r-l+1)*(l+r)/2;}ans=n*k-ans;printf("%lld
",ans);return 0;
}

不要抄袭哦