洛谷P2261 [CQOI2007]余数求和

题意

求
$$\sum_{i=1}^nk\%i$$
数据范围：$n,k \le 10^9$

题解

算法：数论分块

易知
$$k\%i=k- \lfloor \frac{k}{i} \rfloor$$
于是

$$ \begin{aligned} \sum_{i=1}^n k\%i &= \sum_{i=1}^n k- \lfloor \frac{k}{i} \rfloor \\ &=nk-\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor \end{aligned} $$

对$\lfloor \frac{k}{i} \rfloor$部分进行数论分块，其值有$\sqrt{k}$种
对于每种$\lfloor \frac{k}{i} \rfloor$的取值$t$，和为：$t \times$该块元素数$\times$该块平均值

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,k;
int ans;
template <typename T>
inline T Min(T a,T b){
    return a<b?a:b;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    ans=n*k;
    for(int l=1,r;l<=n;l=r+1){
        r=(k/l==0)?n:Min(k/(k/l),n);
        ans-=(k/l)*(r-l+1)*(l+r)/2;
    }
    printf("%lld",ans);
    return 0;
}