phi and phi
题意：
求 a n s ( n ) = ∑ i = 1 n ∑ j = 1 n φ ( i j ) φ ( g c d ( i , j ) ) ans(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(ij)\varphi(gcd(i,j)) ans(n)=∑i=1n∑j=1nφ(ij)φ(gcd(i,j))
Solution:
a
n
s
(
n
)
=
∑
i
=
1
n
∑
j
=
1
n
φ
(
i
j
)
φ
(
g
c
d
(
i
,
j
)
)
=
∑
i
=
1
n
∑
j
=
1
n
φ
(
i
)
φ
(
j
)
g
c
d
(
i
,
j
)
=
∑
k
=
1
n
∑
i
=
1
n
∑
j
=
1
n
φ
(
i
)
φ
(
j
)
k
[
g
c
d
(
i
,
j
)
=
k
]
=
∑
k
=
1
n
∑
i
=
1
n
∑
j
=
1
n
φ
(
i
)
φ
(
j
)
k
[
g
c
d
(
i
k
,
j
k
)
=
1
]
=
∑
k
=
1
n
k
∑
i
=
1
⌊
n
k
⌋
∑
j
=
1
⌊
n
k
⌋
φ
(
i
k
)
φ
(
j
k
)
[
g
c
d
(
i
,
j
)
=
1
]
=
∑
k
=
1
n
k
∑
i
=
1
⌊
n
k
⌋
∑
j
=
1
⌊
n
k
⌋
φ
(
i
k
)
φ
(
j
k
)
∑
d
∣
g
c
d
(
i
,
j
)
μ
(
d
)
=
∑
k
=
1
n
k
∑
d
=
1
⌊
n
k
⌋
μ
(
d
)
∑
i
=
1
⌊
n
k
d
⌋
φ
(
i
k
d
)
∑
j
=
1
⌊
n
k
d
⌋
φ
(
j
k
d
)
=
∑
k
=
1
n
k
∑
d
=
1
⌊
n
k
⌋
μ
(
d
)
(
∑
i
=
1
⌊
n
k
d
⌋
φ
(
i
k
d
)
)
2
ans(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(ij)\varphi(gcd(i,j)) \\ =\sum_{i=1}^{n}\sum_{j=1}^n\varphi(i)\varphi(j)gcd(i,j) \\ =\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(i)\varphi(j)k[gcd(i,j)=k] \\ =\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{ n}\varphi(i)\varphi(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}\varphi(ik)\varphi(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}\varphi(ik)\varphi(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}\varphi(ikd)\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(jkd) \\ =\sum_{k=1}^{n}k\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)(\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(ikd))^2
ans(n)=i=1∑nj=1∑nφ(ij)φ(gcd(i,j))=i=1∑nj=1∑nφ(i)φ(j)gcd(i,j)=k=1∑ni=1∑nj=1∑nφ(i)φ(j)k[gcd(i,j)=k]=k=1∑ni=1∑nj=1∑nφ(i)φ(j)k[gcd(ki,kj)=1]=k=1∑nki=1∑⌊kn⌋j=1∑⌊kn⌋φ(ik)φ(jk)[gcd(i,j)=1]=k=1∑nki=1∑⌊kn⌋j=1∑⌊kn⌋φ(ik)φ(jk)d∣gcd(i,j)∑μ(d)=k=1∑nkd=1∑⌊kn⌋μ(d)i=1∑⌊kdn⌋φ(ikd)j=1∑⌊kdn⌋φ(jkd)=k=1∑nkd=1∑⌊kn⌋μ(d)(i=1∑⌊kdn⌋φ(ikd))2
假设
T
=
k
d
T=kd
T=kd，那么
∑
k
=
1
n
k
∑
d
=
1
⌊
n
k
⌋
μ
(
d
)
(
∑
i
=
1
⌊
n
k
d
⌋
φ
(
i
k
d
)
)
2
=
∑
k
=
1
n
k
∑
k
∣
T
μ
(
T
k
)
(
∑
i
=
1
⌊
n
T
⌋
φ
(
i
T
)
)
2
=
∑
T
=
1
n
∑
k
∣
T
k
μ
(
T
k
)
(
∑
i
=
1
⌊
n
T
⌋
φ
(
i
T
)
)
2
=
∑
T
=
1
n
φ
(
T
)
(
∑
i
=
1
⌊
n
T
⌋
φ
(
i
T
)
)
2
\sum_{k=1}^{n}k\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)(\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(ikd))^2 \\ =\sum_{k=1}^{n}k\sum_{k|T}\mu(\frac{T}{k})(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT))^2 \\ =\sum_{T=1}^{n}\sum_{k|T}k\mu(\frac{T}{k})(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT))^2 \\ =\sum_{T=1}^{n}\varphi(T)(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT))^2
k=1∑nkd=1∑⌊kn⌋μ(d)(i=1∑⌊kdn⌋φ(ikd))2=k=1∑nkk∣T∑μ(kT)(i=1∑⌊Tn⌋φ(iT))2=T=1∑nk∣T∑kμ(kT)(i=1∑⌊Tn⌋φ(iT))2=T=1∑nφ(T)(i=1∑⌊Tn⌋φ(iT))2
之后利用差分加前缀和求解。
代码
#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;
}