AcWing 199. 余数之和【整除分块】

传送门

题解

其中 \(\sum_{i=1}^n\lfloor k/i\rfloor *i\) 可以用整除分块在 \(O(\sqrt{k})\) 的时间复杂度内求出来。

代码

int n,k;
LL ans;

int main(){
    scanf("%d%d",&n,&k);
    ans=1ll*n*k;
    for(int l=1,r;l<=min(n,k);l=r+1){
        r=min(k/(k/l),n);
        ans-=1ll*(l+r)*(r-l+1)/2*(k/l);
    }
    printf("%lld\n",ans);
    return 0;
}

AcWing 199. 余数之和【整除分块】

原文：https://www.cnblogs.com/BakaCirno/p/12955503.html