UVALive

给定$n,k$$(1leqslant n,kleqslant 10^9)$，计算$sumlimits _{i=1}^nk: mod:i$

通过观察易发现$k\%i=k-left lfloor frac{k}{i} ight floor*i$，因此我们考虑把$left lfloor frac{k}{i} ight floor$的值相同的$i$分成一组直接求和，复杂度为$O(sqrt{n})$。

整除分块原理（选自某dalao博客）

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,k;

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