51Nod 1594

Description

F(n)=∑ni=1∑nj=1ϕ(ϕ(i),ϕ(j)) F ( n ) = ∑ i = 1 n ∑ j = 1 n ϕ ( ϕ ( i ) , ϕ ( j ) )

其中 ϕ ϕ 表示歐拉函數。歐拉函數 ϕ(n) ϕ ( n ) 是不超過n的數中與n互質的數的數目。

ϕ(ϕi,ϕj) ϕ ( ϕ i , ϕ j ) 表示i,j歐拉函數值的最大公約數的歐拉函數值.

給出n，求F(n)的值。

Input

一行，包含正整數T，表示資料組數。T<=5

接下來T行每行一個正整數n。n<=2*10^6

Output

共T行，每行包含一個答案。

Input示例

1
1
           

Output示例

1
           

Solution

莫比烏斯反演。。。蒟蒻不會寫系列

依題意，有

Ans=∑ni=1∑nj=1ϕ(ϕi),ϕ(j)) A n s = ∑ i = 1 n ∑ j = 1 n ϕ ( ϕ i ) , ϕ ( j ) )

枚舉其gcd，

Ans=∑nd=1ϕ(d)∗∑ni=1∑nj=1[gcd(ϕ(i),ϕ(j)=d] A n s = ∑ d = 1 n ϕ ( d ) ∗ ∑ i = 1 n ∑ j = 1 n [ g c d ( ϕ ( i ) , ϕ ( j ) = d ]

設 g(d)=∑ni=1∑nj=1[d|gcd(ϕ(i),ϕ(j))] g ( d ) = ∑ i = 1 n ∑ j = 1 n [ d | g c d ( ϕ ( i ) , ϕ ( j ) ) ]

f(d)=∑ni=1∑nj=1[gcd(ϕ(i),ϕ(j))=d] f ( d ) = ∑ i = 1 n ∑ j = 1 n [ g c d ( ϕ ( i ) , ϕ ( j ) ) = d ]

則有

g(d)=∑d|kf(k) g ( d ) = ∑ d | k f ( k )

f(n)=∑n|dμ(dn)∗g(d) f ( n ) = ∑ n | d μ ( d n ) ∗ g ( d )

Ans=∑nd=1ϕ(d)∗f(d) A n s = ∑ d = 1 n ϕ ( d ) ∗ f ( d )

f(d)可以在O（nln(n)）的時間内求出

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

#define N 2000020
#define M 2000000
#define LL long long

LL t[N],prime[N],phi[N],mu[N];
LL f[N],g[N];
int ti,n;

void pre()
{
    phi[]=mu[]=;
    memset(t,,sizeof(t));
    memset(prime,,sizeof(prime));
    for (int i=;i<=M;i++)
    {
        if (t[i]==) 
        {
            prime[++prime[]]=i;
            mu[i]=-; phi[i]=i-;
        }
        for (int j=;j<=prime[];j++)
        {
            int k=i*prime[j];
            if (k>M) break;
            t[k]=;
            if (i%prime[j]==)
            {
                mu[k]=;
                phi[k]=phi[i]*prime[j];
                break;
            }
            mu[k]=-mu[i];
            phi[k]=phi[i]*phi[prime[j]];
        }
    }
}

LL solve(int n)
{
    memset(t,,sizeof(t));
    memset(g,,sizeof(g));
    memset(f,,sizeof(f));
    for (int i=;i<=n;i++)
      t[phi[i]]++;
    for (int d=;d<=n;d++)
      for (int i=;i<=n/d;i++)
        g[d]+=t[i*d];
    for (int i=;i<=n;i++)
      g[i]=g[i]*g[i];
    for (int d=;d<=n;d++)
      for (int i=;i<=n/d;i++)
        f[d]+=mu[i]*g[i*d];
    //for (int i=1;i<=n;i++)
    //  printf("%d %d %d %d %d\n",i,phi[i],mu[i],g[i],f[i]);
    LL ans=;
    for (int i=;i<=n;i++)
      ans+=phi[i]*f[i];
    return ans;
}

int main()
{
    pre();
    scanf("%d",&ti);
    for (int ii=;ii<=ti;ii++)
    {
        scanf("%d",&n);
        printf("%lld\n",solve(n));
    }
    return ;
}