瞎起的名字……不要吐槽不符合反演的定义之类的……
首先有 \[\begin{align*} & \sum\limits_{i=1}^n\sum\limits_{d|i}\gcd(d,\dfrac i d) \\ = & \sum\limits_{d=1}^n\sum\limits_{id \le n}\gcd(d,i) \\ = & \sum\limits_{k\le n} k \sum\limits_{dk\le n}\sum\limits_{idk\le n} [\gcd(d,i)=1] \end{align*}\]
然鹅推到这里你会发现自己推错了，由于两个都除以了 \(k\)，所以上界需要修正。 \[\begin{align*} & \sum\limits_{k^2\le n} k \sum\limits_{dk^2\le n}\sum\limits_{idk^2\le n} [\gcd(d,i)=1] \\ = & \sum\limits_{k^2\le n} k \sum\limits_{dk^2\le n}\sum\limits_{j | \gcd(d,i)} \mu(j) \\ = & \sum\limits_{k^2\le n} k \sum\limits_{j^2 k^2\le n} \mu(j) \sum\limits_{dj^2 k^2 \le n}\left\lfloor\dfrac n{dj^2 k^2}\right\rfloor \\ = & \sum\limits_{k=1}^{\lfloor\sqrt n\rfloor} k \sum\limits_{j=1}^{\left\lfloor\sqrt{\left\lfloor \frac n {k^2}\right\rfloor}\right\rfloor} \mu(j) \sum\limits_{d = 1}^{\left\lfloor\frac n {j^2 k^2}\right\rfloor} \left\lfloor\dfrac n{dj^2 k^2}\right\rfloor \end{align*}\]
后面那个东西其实就是约数个数前缀和，不过用这个方法的话还要带个杜教筛。
复杂度证明： \[ \sum\limits_{i=1}^{\lfloor\sqrt n\rfloor} \sqrt{\frac{n}{i^2}} = \sum\limits_{i=1}^{\lfloor\sqrt n\rfloor} \frac{\sqrt n}i = O(\sqrt n \log n) \]
故这个方法的复杂度是 \(O(\sqrt n \log n + n^{2/3})\) 的。
另一种方法：利用欧拉函数的性质 \(\varphi * \mathbb 1 = \text{ID}\)。
证明：
原式即 \(\sum\limits_{d | n} \varphi(d) = n\)。
考虑将 \([1,n]\) 中的所有数按照和 \(n\) 的 \(\gcd\) 分类，即 \(C_d = \{x|x \in [1,n],\gcd(x,n) = d\}\)。
那么显然每个数都有唯一对应的 \(C_d\)，于是有 \(\sum\limits_{d | n} |C_d| = n\)（注意 \(d|n\) 时才有贡献）。
然后又发现，\(|C_d| = \sum\limits_{i = 1}^n [\gcd(i,n) = d] = \sum\limits_{i = 1}^{\frac n d} [\gcd(i,\dfrac n d) = 1] = \varphi(\dfrac n d)\)。
证毕。
重新来过： \[\begin{align*} & \sum\limits_{i=1}^n\sum\limits_{d|i}\gcd(d,\dfrac id) \\ = & \sum\limits_{d=1}^n\sum\limits_{id\le n}\gcd(d,i) \\ = & \sum\limits_{d=1}^n\sum\limits_{id\le n}\sum\limits_{k|\gcd(d,i)}\varphi(k) \\ = & \sum\limits_{k^2\le n}\varphi(k)\sum\limits_{dk^2\le n}\left\lfloor\dfrac n{dk^2}\right\rfloor \\ = & \sum\limits_{k=1}^{\lfloor\sqrt n\rfloor}\varphi(k)\sum\limits_{d=1}^{\left\lfloor\frac n{k^2}\right\rfloor}\left\lfloor\dfrac n{dk^2}\right\rfloor \end{align*}\]
线性筛之后暴力计算……
该做法的复杂度是 \(O(\sqrt n \log 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
using namespace std;
const long long N = 1e11;
const int MX = 32e4;
long long n;
int mx,vis[MX + 5],cnt,prime[MX + 5],phi[MX + 5];
long long ans,cur,bound;
int main()
{
freopen("gcd.in","r",stdin),freopen("gcd.out","w",stdout);
scanf("%lld",&n),mx = sqrt(n),phi[1] = 1;
for(register int i = 2;i <= mx;++i)
{
if(!vis[i])
phi[prime[++cnt] = i] = i - 1;
for(register int j = 1;j <= cnt && i * prime[j] <= mx;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for(register int i = 1;i <= mx;++i)
{
cur = 0,bound = n / i / i;
for(register long long l = 1,r;l <= bound;l = r + 1)
{
r = bound / (bound / l);
cur += (bound / l) * (r - l + 1);
}
ans += cur * phi[i];
}
printf("%lld\n",ans);
}