[51Nod 1594] Gcd and Phi

Description

求 ANS=∑i=1n∑j=1nφ(gcd(φ(i),φ(j)))

n<=2*10^6

Solution

一道極裸的反演題。

設 p(k)=∑[φ(i)=k]

f(d)=∑∑[gcd(φ(i),φ(j))=d]=∑∑[gcd(i,j)=d]p(i)p(j)

都是套路

g(d)=∑i=1ndf(id)

ANS=∑d=1nφ(d)f(d)=∑d=1nφ(d)∑i=1ndμ(i)g(id)

g 怎麼求？

如果沒有p，那麼很明顯 g(d)=⌊nd⌋2

但是有 p 怎麼辦？

不虛

再設S(d)=∑i=1ndp(id)，也就是單獨 i 的選法

g(d)=S(d)2

， i,j 乘起來

ANS=∑d=1nφ(d)∑i=1ndμ(i)S(id)2

因為 ∑i=1nni≈nlog(n)

是以直接暴力做就是 O(nlogn) 的，注意卡常。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long 
#define N 2000005
using namespace std;
int mu[N],pr[N],n,t,l,phi[N];
LL s[N],p[N];
bool bz[N];
void prp(int n)
{
    l=;
    mu[]=phi[]=p[]=;
    fo(i,,n)
    {   
        if(bz[i]==) pr[++l]=i,mu[i]=-,phi[i]=i-;
        p[phi[i]]++;
        for(int j=;j<=l&&i*pr[j]<=n;j++)
        {
            bz[i*pr[j]]=;
            if(i%pr[j]==) 
            {
                mu[i*pr[j]]=;
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            phi[i*pr[j]]=phi[i]*(pr[j]-);
            mu[i*pr[j]]=-mu[i];
        }
        bz[i]=;
    }
    fo(d,,n)
    {
        s[d]=;
        fo(i,,n/d) s[d]+=p[i*d];
    }
}
int main()
{
    cin>>t;
    while(t-->)
    {
        scanf("%d",&n);
        LL ans=;
        prp(n);
        fo(d,,n)
        {
            LL s1=;
            p[d]=;
            fo(i,,n/d) s1+=mu[i]*s[i*d]*s[i*d];
            ans+=s1*phi[d];
        }
        printf("%lld\n",ans);
    }
}