题目传送门(BZOJ)
>原文链接<

题解:

推式子 :

枚举$\gcd(i, j)$

则原式可化为
$\sum\limits_{p=1}^{n} \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \varphi(p)[\gcd(i,j)=p]$
我们把$\varphi(p)$提到前面化为
$\sum\limits_{p=1}^{n} \varphi(p)\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}[\gcd(i,j)=p]$
把$[\gcd(i,j)=p]$ 中的$p$除到前面,则原式可化为
$\sum\limits_{p=1}^{n} \varphi(p)\sum\limits_{i=1}^{\lfloor \frac{n}{p}\rfloor} \sum\limits_{j=1}^{\lfloor \frac{n}{p}\rfloor}[\gcd(i,j)=1]$
设函数$f(n)$表示 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1]$
则原式可视为 $\sum\limits_{p=1}^{n} \varphi(p)\times f(\lfloor \frac{n}{p}\rfloor)$
考虑化简函数$f(n)$

这个函数和欧拉函数有些相似。

首先我们只考虑$i\ge j$的情况;

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}[\gcd(i,j)=1] => \sum\limits_{i=1}^{n}\varphi(i)$

同理,我们发现只考虑$i\le j$的情况,
也为$\sum\limits_{j=1}^{n}\varphi(j)$
两种情况同时考虑,$i=j$的情况重复,去重$f(n)$最终可化简为$2 \times\sum\limits_{i=1}^{n}\varphi(i) -1$
综上所述,我们可以发现$ans = \sum\limits_{p=1}^{n} \varphi(p) \times 2 \times\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i) -1$
现在我们有了一个$O(n)$的方法求解$ans$ 但是数据组数为$T = 5000$ .

我们需要更加优化的方法才能解决问题。

我们先把$S_\varphi$处理出来

再把每个答案$O(\sqrt n)$处理,根号求和。再乘上前面相应的$\varphi(p)$

故总的时间复杂度为$O(n + T\times \sqrt n)

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#define ll long longusing namespace std;const int N = 10000000;int phi[N], pr[N];bool np[N];ll s[N];void init() { s[1] = phi[1] = 1; for(int i = 2; i < N; i ++ ) { if(!np[i]) { pr[++*pr] = i; phi[i] = i-1; } for(int j = 1; j <= *pr && i*pr[j] < N; j ++ ) { np[i*pr[j]] = 1; if(i%pr[j] == 0) { phi[i*pr[j]]=phi[i]*pr[j]; break; } else phi[i*pr[j]] = phi[i]*(pr[j]-1); } s[i] = s[i-1]+phi[i]; }}int main() { int t; scanf("%d", &t); init(); while(t -- ) { int n; ll ans=0; scanf("%d", &n); int lst = 0; for(int p = 1; p <= n;p = lst+1) { lst = n/(n/p); ans += (s[lst]-s[p-1])*(s[n/p]*2-1); } printf("%lld\n", ans); }}