phi and phi（莫比乌斯反演+公式）

phi and phi

题意：

求$ans(n)={\sum }_{i=1}^n{\sum }_{j=1}^n\phi (ij)\phi (gcd(i,j))$

Solution:

$$\begin{gathered} ans(n)=\sum _{i=1}^n\sum _{j=1}^n\phi (ij)\phi (gcd(i,j)) \\ =\sum _{i=1}^n\sum _{j=1}^n\phi (i)\phi (j)gcd(i,j) \\ =\sum _{k=1}^n\sum _{i=1}^n\sum _{j=1}^n\phi (i)\phi (j)k[gcd(i,j)=k] \\ =\sum _{k=1}^n\sum _{i=1}^n\sum _{j=1}^n\phi (i)\phi (j)k[gcd(\frac{i}{k},\frac{j}{k})=1] \\ =\sum _{k=1}^{n}k\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }\phi (ik)\phi (jk)[gcd(i,j)=1] \\ =\sum _{k=1}^{n}k\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }\phi (ik)\phi (jk)\sum _{d|gcd(i,j)}\mu (d) \\ =\sum _{k=1}^{n}k\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\mu (d)\sum _{i=1}^{\lfloor \frac{n}{kd}\rfloor }\phi (ikd)\sum _{j=1}^{\lfloor \frac{n}{kd}\rfloor }\phi (jkd) \\ =\sum _{k=1}^{n}k\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\mu (d)(\sum _{i=1}^{\lfloor \frac{n}{kd}\rfloor }\phi (ikd){)}^2 \end{gathered}$$
假设$T=kd$，那么
$$\begin{gathered} \sum _{k=1}^{n}k\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\mu (d)(\sum _{i=1}^{\lfloor \frac{n}{kd}\rfloor }\phi (ikd){)}^2 \\ =\sum _{k=1}^{n}k\sum _{k|T}\mu (\frac{T}{k})(\sum _{i=1}^{\lfloor \frac{n}{T}\rfloor }\phi (iT){)}^2 \\ =\sum _{T=1}^n\sum _{k|T}k\mu (\frac{T}{k})(\sum _{i=1}^{\lfloor \frac{n}{T}\rfloor }\phi (iT){)}^2 \\ =\sum _{T=1}^n\phi (T)(\sum _{i=1}^{\lfloor \frac{n}{T}\rfloor }\phi (iT){)}^2 \end{gathered}$$
之后利用差分加前缀和求解。

代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

const int mod=1e9+7;
const int N=1e6;
int prime[N+5],notPrime[N+5],cnt=0;
ll sum[N+5],phi[N+5];
void initPhi()
{
   
    phi[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notPrime[i])
        {
   
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notPrime[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
   
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
int n;
int main()
{
   
    initPhi();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
   
        ll preSum=0;
        for(int j=1;j<=n/i;j++)
        {
   
            preSum=(preSum+phi[i*j])%mod;
            sum[i*j]=(sum[i*j]+preSum*preSum%mod*phi[i]%mod)%mod;
            if(i*j+i<=n)sum[i*j+i]=(sum[i*j+i]-preSum*preSum%mod*phi[i]%mod+mod)%mod;
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++)
    {
   
        res=(res+sum[i])%mod;
        printf("%lld\n",res);
    }
    return 0;
}