Luogu P2261 [CQOI2007]余数求和

题目描述：

给出正整数 n 和 k，请计算
G(n, k) = \sum_{i = 1}^n k \bmod i
其中 k\bmod i 表示 k 除以 i的余数。

n,k\leq10^9

Solution：

有
k \bmod i= k-\lfloor \frac{k}{i} \rfloor*i
利用整除分块将 \lfloor \frac{k}{i} \rfloor 分为一块，利用等差数列即可在 O(\sqrt{n}) 的复杂度求出答案

#include<bits/stdc++.h>
#define ll long long
ll n,k;
ll  t;
int main(){
    scanf("%lld%lld",&n,&k);
    ll ans=0;
    if(n>k) ans+=1ll*k*(n-k);
    n=std::min(n,k);
    for(ll l=1,r;l<=n;l=r+1){
        r=k/(k/l);
        r=std::min(n,r);
        ans+=k*(r-l+1)-(r-l+1)*(r+l)/2*(k/l);
        t++;
    }
    printf("%lld",ans);
    return 0;
}