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;
}
0 条评论