Luogu P2424 约数和

题目描述

对于一个数 X，函数 f(X) 表示 X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个 X，Smart 可以很快的算出 f(X)。现在的问题是，给定两个正整数 X,Y(X<Y)Smart 希望尽快地算出 f(X)+f(X+1)+……+f(Y)的值，你能帮助 Smart 算出这个值吗？

Solution

发现对每一个整除分块值 w=\frac{n}{i} 来说，

w 即为该分块中的每一个数 在 1\to n 的因数 中出现的次数

然后求个和就好了

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