zcmimi's blog
avatar
zc
2020-03-12 18:02:00
  • 本文总阅读量
查看原题

点击跳转

可以先转化为前缀和再相减

问题变为了求:

\sum_{i=1}^n \sum_{j|i}j

考虑每个约数d,它的贡献次数为\left \lfloor \frac nd\right \rfloor

那么答案就是

\sum_{d=1}^n d\left \lfloor \frac nd\right \rfloor

直接数论分块即可

#include<cstdio>
typedef long long ll;
ll calc(int n){
    ll ans=0;
    for(ll l=1,r=0;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(r-l+1)*(l+r)/2*(n/l);
    }
    return ans;
}
int main(){
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%lld\n",calc(r)-calc(l-1));
}
LG 2424 约数和
comment评论
Search
search