P2424 约数和

题意：设$f(x)$为$x$的约数和，求$[L,R]$的$f$之和 ------------ 并不用约数和定理 参考[P1403](https://www.luogu.org/problemnew/show/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; } ```