[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]=sumlimits_{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}^{lfloorfrac{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}^{lfloorfrac{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} ^{lfloorfrac{n}{d}rfloor}sum_{i=1}^{lfloor{frac{n}{dd'}}rfloor} sum_{j=1}^{lfloorfrac{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} ^{lfloorfrac{n}{d}rfloor} mu(d') sum_{i=1}^{lfloor{frac{n}{dd'}}rfloor} sum_{j=1}^{lfloorfrac{n}{dd'}rfloor} p[i d d'] times p[j d d'] end{align}$$

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

显然，

$$begin{align} G(x) &= sumlimits_{i=1}^{lfloor frac{n}{x} rfloor } sumlimits_{j=1}^{lfloor frac{n}{x} rfloor} p[ix] times p[jx] \ G(x) &= sumlimits_{i=1}^{lfloor frac{n}{x} rfloor } p[ix] sumlimits_{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} ^{lfloorfrac{n}{d}rfloor} mu(d') sum_{i=1}^{lfloor{frac{n}{dd'}}rfloor} sum_{j=1}^{lfloorfrac{n}{dd'}rfloor} p[i d d'] times p[j d d']\ F(n) &= sum_{d=1}^{n} varphi(d) sum_{d'=1} ^{lfloorfrac{n}{d}rfloor} mu(d') times G(dd') end {align}$$

这个东西也可以$mathcal{O}(n log_2 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
41
42
43
44
45
46
47
48
49
50
51
52
53

#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 ()
{
    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("%lldn",ans);
}
int main()
{
    scanf("%d",&T);
    while(T--) solve();
}