求前n个正整数的约数之和

求\(\sum_{i=1}^{n}\sigma \left ( i\right ),i\leq 10^{12},\sigma \left ( n\right )=\sum_{d|n}d\)

解：\(\sum_{i=1}^{n}\sigma \left ( i\right )=\sum_{i=1}^{n}\sum_{d|i}d=\sum_{i=1}^{n}\sum_{d=1}^{n}\left [ d|i\right ]*d=\sum_{i=1}^{n}i*\sum_{i=1}^{n}\left [ i|d\right ]=\sum_{i=1}^{n}i*\left \lfloor \frac{n}{i}\right \rfloor\)

代码：

 1 ll n,ans;
 2 int main()
 3 {
 4     scanf("%lld",&n);
 5     for(ll l=1ll,r;l<=n;l=r+1ll){
 6         r=min(n/(n/l),n);
 7         ans = ans + (n/l)*((l+r)*(r-l+1)/2);
 8     }
 9     printf("%lld\n",ans);
10     return 0;
11 }

也可以这样化简：

\(\sum_{i=1}^{n}\sum_{d|n}d=\sum_{i=1}^{n}\sum_{d=1}^{\left \lfloor \frac{n}{i}\right \rfloor}d=\sum_{i=1}^{n}\frac{\left ( 1+\left \lfloor \frac{n}{i}\right \rfloor\right )*\left \lfloor \frac{n}{i}\right \rfloor}{2}\)

\(\sum_{i=1}^{n}\frac{\left ( 1+\left \lfloor \frac{n}{i}\right \rfloor\right )*\left \lfloor \frac{n}{i}\right \rfloor}{2}=\sum_{i=1}^{n}i*\left \lfloor \frac{n}{i}\right \rfloor\)

求前n个正整数的约数之和

原文：https://www.cnblogs.com/wsy107316/p/12773987.html