洛谷P2261 [CQOI2007]余数求和

传送门

题目要求$sum_{i=1}^n k\%i$

那么就是$sum_{i=1}^n k\%i=sum_{i=1}^n k-i*leftlfloorfrac{k}{i} ight floor=n*k-sum_{i=1}^n i*leftlfloorfrac{k}{i} ight floor$

那么我们可以枚举$leftlfloorfrac{k}{i} ight floor$的取值，因为个数只有$sqrt{n}$，所以时间复杂度是$O(sqrt{n})$

代码短小精炼

//minamoto
#include<cstdio>
#define ll long long
#define min(a,b) ((a)<(b)?(a):(b))
int main(){
    ll n,k;scanf("%lld%lld",&n,&k);
    ll ans=n*k;
    for(ll l=1,r;l<=n;l=r+1){
        r=(k/l)?min(k/(k/l),n):n;
        ans-=k/l*(r-l+1)*(l+r)/2;
    }
    printf("%lld
",ans);
    return 0;
}