题解 P2398 【GCD SUM】
FifthAxiom
·
·
题解
题目大意
给定正整数n，求
\sum_{i = 1}^n\sum_{j = 1}^n\gcd(i,j)\quad(0)
前置知识
欧拉函数：定义数论函数\phi（数论函数指定义域为正整数，值域为具有特定意义的数集的一类函数），有
\phi(n)=\begin{cases}1\quad (n=1) \\ \text{1到n-1内与n互质的数的个数}\quad otherwise\end{cases}
欧拉函数有一个奇怪的性质
\sum_{d|n}\phi(d)=n
下面我们简单证明一下
若$p$是素数，显然有
$$\phi(p)=p-1$$
那么，对于正整数$kp$，与其不互质的数只有$1,p,2p,3p\dots, kp$，故
$$\phi(kp)=k(p-1) \quad(1)$$
对于素数幂$p^k$，由$(1)$可知
$$\phi(p^k)=p^{k-1}(p-1)=p^k-p^{k-1}$$
对于
$$\sum_{d|p^k}\phi(d) \quad(2)$$
显然，$d$只能取$1,p,p^2,p^3\dots,p^k$。那么有
$$\begin{aligned}&(2)\\&=(\sum_{d=1}^k\phi(p^d))+1\\&=(\sum_{d=1}^kp^d-p^{d-1})+1\\&=p^k-p^{k-1} +p^{k-1}-p^{k-2}+\dots -p+p-1+1\\&=p^k\end{aligned}$$
因为$\phi$是积性函数，即若$n\perp m$，$\phi(nm)=\phi(n)\phi(m)$，由正整数唯一分解定理可知$\sum_{d|n}\phi(d)=n$。
Q.E.D.
~~这个证明窝自己搞出来的，嘿嘿~~
那么回到本题，有
$$\begin{aligned}&(0)\\&=\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d|\gcd(i,j)}\phi(d)\\&=\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d|i,d|j}\phi(d) \quad\text{d|gcd(i,j)可以写成d|i,d|j，不难理解吧}\\&=\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d=1}^n\phi(d)[d|i][d|j] \quad\text{[P]中若P为真则[P]=1，否则[P]=0}\\&=\sum_{d=1}^n\phi(d)\sum_{i=1}^n\sum_{j=1}^n[d|i][d|j]\\&=\sum_{d=1}^n\phi(d)\lfloor\dfrac{n}{d}\rfloor^2 \end{aligned}$$
至此，我们可以线性筛出$1$到$n$中的$\phi$，然后把最后的柿子for一遍就行啦（当然用整除分块更好，但此题里$n$的范围太小，直接搞也可以）
## 代码
```cpp
#include <cstdio>
#include <cstring>
const int MAXN = 100010;
int prime[MAXN], v[MAXN], phi[MAXN], sumPhi[MAXN], cnt, n;
void eular(int n) {//线性筛筛欧拉函数
memset(v, 0, sizeof(v));
sumPhi[1] = phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!v[i]) {
prime[++cnt] = v[i] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt; j++) {
if (prime[j] > v[i] || i * prime[j] > n) break;
v[i * prime[j]] = prime[j];
phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
}
sumPhi[i] = sumPhi[i - 1] + phi[i];//求欧拉函数的前缀和，如果整除分块的话就要用
}
}
int main() {
scanf("%d", &n);
eular(n);
long long ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {//这里是整除分块写法，如果不懂可以直接for 1 to n
r = n / (n / l);
ans += (long long) (sumPhi[r] - sumPhi[l - 1]) * (n / l) * (n / l);
}
printf("%lld\n", ans);
return 0;
}
```
谢谢大家观看资瓷！
20191022 update:修复题解区markdown轩然