P2424

发表于 分类于
约数和

约数和

一下就知道前缀和作差。

所以我们需要求的就是：

$$
\begin{aligned}
& \sum_{i=1}^{n}\sigma(i)
\\
=& \sum_{i=1}^{n}\sum_{d\mid i}d
\\
=& \sum_{d=1}d\left\lfloor\dfrac{n}{d}\right\rfloor
\end{aligned}
$$

中间那一步可以直接根据其意义来。。。

实际上就是 $\sigma=\mathbf{id}\ast \mathbf{1}$ 的应用。。。

时间复杂度 $O(\sqrt{n})$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

inline ll S(ll x) {return x*(x+1)/2;}

inline ll F(ll x) {
  ll r=0;
  for(ll i=1,j;i<=x;i=j+1) {
    j=x/(x/i);r=r+(S(j)-S(i-1))*(x/i);
  }
  return r;
}

int main() {

  ll l,r;l=read();r=read();

  write(F(r)-F(l-1));

  return 0;
}