[51NOD 1594] Gcd and Phi

题目大意：给定n，求$F(n) = \sum{i=1}^{n} \sum{j=1}^{n} \varphi( \gcd(\varphi(i),\varphi(j)))​$ ，多组数据。

$n \leqslant 10^5 ,T \leqslant 5$

$$F(n) = \sum_{i=1}^{n} \sum_{j=1}^{n} \varphi( \gcd(\varphi(i),\varphi(j)))$$

不妨设$p[x]=\sum\limits_{i=1}^{n} [\varphi(i)==x]$

不妨枚举$\varphi$的取值，易作如下变形

$$\begin{align} F(n) &= \sum_{i=1}^{n} \sum_{j=1}^{n} \varphi( \gcd(\varphi(i),\varphi(j)) ) \\ F(n) &= \sum_{i=1}^{n} \sum_{j=1}^{n} \varphi(\gcd(i,j)) \times p[i] \times p[j] \\ F(n) &= \sum_{i=1}^{n} \sum_{j=1}^{n} p[i] \times p[j] \times \sum_{d|i,d|j}\varphi(d) \times \varepsilon(\gcd(\frac{i}{d},\frac{j}{d})) \\ F(n) &=\sum_{d=1}^{n} \sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} \varphi(d) \times p[i d] \times p[j d] \times \varepsilon(\gcd(i,j)) \\ F(n) &=\sum_{d=1}^{n} \sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} \varphi(d) \times p[i d] \times p[j d] \times \sum_{d'|i,d'|j} \mu(d') \\ F(n) &=\sum_{d=1}^{n} \sum_{d'=1} ^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor{\frac{n}{dd'}}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{dd'}\rfloor} \mu(d') \times \varphi(d) \times p[i d d'] \times p[j d d'] \\ F(n) &=\sum_{d=1}^{n} \varphi(d) \sum_{d'=1} ^{\lfloor\frac{n}{d}\rfloor} \mu(d') \sum_{i=1}^{\lfloor{\frac{n}{dd'}}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{dd'}\rfloor} p[i d d'] \times p[j d d'] \end{align}$$

不妨设$G(x)=\sum\limits{i=1}^{\lfloor \frac{n}{x} \rfloor } \sum\limits{j=1}^{\lfloor \frac{n}{x} \rfloor} p[ix] \times p[jx]​$

显然，

$$\begin{align} G(x) &= \sum\limits_{i=1}^{\lfloor \frac{n}{x} \rfloor } \sum\limits_{j=1}^{\lfloor \frac{n}{x} \rfloor} p[ix] \times p[jx] \\ G(x) &= \sum\limits_{i=1}^{\lfloor \frac{n}{x} \rfloor } p[ix] \sum\limits_{j=1}^{\lfloor \frac{n}{x} \rfloor} p[jx] \\ G(x) &=(\sum_{i=1}^{\lfloor \frac{n}{x}\rfloor} p[ix])^2 \end{align}$$

这个东西可以$\mathcal{O}(n \ log_2 n)$求。

我们看看$F(n)$变成了什么

$$\begin {align} F(n) &=\sum_{d=1}^{n} \varphi(d) \sum_{d'=1} ^{\lfloor\frac{n}{d}\rfloor} \mu(d') \sum_{i=1}^{\lfloor{\frac{n}{dd'}}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{dd'}\rfloor} p[i d d'] \times p[j d d']\\ F(n) &= \sum_{d=1}^{n} \varphi(d) \sum_{d'=1} ^{\lfloor\frac{n}{d}\rfloor} \mu(d') \times G(dd') \end {align}$$

这个东西也可以$\mathcal{O}(n \log_2 n)$求。

好，做完了。

代码如下

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN=2E6+10;
int phi[MAXN],mu[MAXN],n,pri[MAXN],tot,p[MAXN],T;
ll f[MAXN],ans;
bool vis[MAXN];
void solve()
{
    scanf("%d",&n);tot=0;
    memset(vis,0,sizeof vis);
    memset(f,0,sizeof f);
    memset(p,0,sizeof p);
    phi[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=tot&&pri[j]*i<=n;j++)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0) {mu[i*pri[j]]=0;phi[i*pri[j]]=phi[i]*pri[j];break;}
            else mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<=n;i++) ++p[phi[i]];
    ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            f[i]+=p[j];
    for(int i=1;i<=n;i++) f[i]=f[i]*f[i];
    for(int i=1;i<=n;i++)
        if(mu[i])
            for(int j=1;i*j<=n;j++)
                ans+=mu[i]*f[i*j]*phi[j];
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&T);
    while(T--) solve();
}