P2398

发表于 更新于 分类于
GCD SUM

GCD SUM

推就完了。

$$\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)\\= & \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}[\gcd(i,j)=d]d\\ =& \sum_{d=1}d\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]\end{aligned}$$

后面是不知道哪里的原题了反正。。。算了还是写一下。。。

$$\begin{aligned}=&\sum_{d=1}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\\ =& \sum_{d=1}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k\mid \gcd(i,j)}\mu(k)\\=& \sum_{d=1}d\sum_{k=1}\mu(k)(\lfloor\dfrac{n}{kd}\rfloor)^2\end{aligned}$$

接下来设 $T=kd$，则 $k=\dfrac{T}{d}$。

$$\begin{aligned}=& \sum_{d=1}d\sum_{d\mid T}\mu(\dfrac{T}{d})(\lfloor\dfrac{n}{T}\rfloor)^2\\ =& \sum_{T=1}\sum_{d\mid T}d\mu(\dfrac{T}{d})(\lfloor\dfrac{n}{T}\rfloor)^2\end{aligned}$$

然后我们知道有 $\mathbf{id} * \mu=\varphi * \mathbf{1} * \mu=\varphi$。

所以说上式就是：

$$\sum_{T=1}\varphi(T)(\lfloor\dfrac{n}{T}\rfloor)^2$$

直接求 $\varphi$ 前缀和，然后数论分块即可。

然而，上面的全都是吃多了的做法。

我们都已经知道了 $\mathbf{id}=1*\varphi$ 了，为什么还要舍近求远的去用 $\mu$ 来反演呢？

于是原式直接变为：

$$\begin{aligned}& \sum_{i=1}\sum_{j=1}\sum_{d\mid \gcd(i,j)}\varphi(d)\\ =& \sum_{d=1}\varphi(d)(\lfloor\dfrac{n}{d}\rfloor)^2\end{aligned}$$

其实这里第一个吃多了的做法就是我一开始的做法，事实证明只要结论足够熟练，推的七拐八绕也能再推回来，但是这其实还是体现了一个对题目的敏感度低，再加上平常套路做太多了，容易丧失这种比较简便的思维。

更重要的是，式子一旦麻烦起来，有时候你真的是推不出来（很容易推错，比如幽灵乐团）。

虽然这是一道没有太大难度的题目，但希望来这里看的人能够引以为戒。

时间复杂度 $O(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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,ans,cnt;

ll phi[N+5],sphi[N+5],prime[N+5];
bool f[N+5];

inline void Init() {
  phi[1]=1;f[1]=1;
  for(ll i=2;i<=n;i++) {
    if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;}
    for(ll j=1;j<=cnt&&prime[j]*i<=n;j++) {
      f[i*prime[j]]=1;
      if(i%prime[j]==0) {phi[i*prime[j]]=prime[j]*phi[i];break;}
      phi[i*prime[j]]=phi[i]*phi[prime[j]];
    }
  }
  for(ll i=1;i<=n;i++) sphi[i]=sphi[i-1]+phi[i];
}

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--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  n=read();Init();

  for(ll i=1,j;i<=n;i=j+1) {
    j=n/(n/i);ans+=(sphi[j]-sphi[i-1])*(n/i)*(n/i);
  }

  write(ans);

  return 0;
}