题目传送门(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); }}