P2424 约数和

2018-09-25 09:09:31


题意:设 $f(x)$ 为 $x$ 的约数和,求 $[L,R]$ 的 $f$ 之和


并不用约数和定理

参考P1403

计算 $[1,R]$ 的约数和减去 $[1,L-1]$ 的即可

设 $g(x)$ 表示 $[1,x]$ 的约数个数和

那么每个 $i(i∈[1,x])$ 的贡献就是 $floor(x/i)$

用类似分块的思想可以做到 $O(sqrt(n))$

记 $s[n]=∑f(i),i∈[1,n]$

那么也可以用上述方法求解

每次乘上 $(i+j)/2$ 就好了

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll L,R;
inline ll solve(ll n,ll ans=0)
{
    for (ll i=1,j;i<=n;i=j+1)
    {
        j=n/(n/i);
        ans+=(n/i)*(j-i+1)*(i+j)/2;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&L,&R);
    printf("%lld\n",solve(R)-solve(L-1));
    return 0;
}