当前位置 博文首页 > cjmHK的博客：tsy‘s number（莫比乌斯反演+狄利克雷卷积+欧拉筛
再化简公式前，先介绍一下强化版的欧拉函数积性公式
?
(
n
m
)
=
?
(
n
)
?
(
m
)
G
C
D
(
n
,
m
)
?
(
G
C
D
(
n
,
m
)
)
\phi(nm)=\phi(n)\phi(m)\frac{GCD(n,m)}{\phi(GCD(n,m))}
?(nm)=?(n)?(m)?(GCD(n,m))GCD(n,m)?
如下是详细的化简过程
原式
=
∑
i
=
1
n
∑
j
=
1
n
∑
k
=
1
n
j
k
2
?
(
g
c
d
(
i
,
j
,
k
)
)
= \sum\limits _{i=1}^{n}\sum\limits _{j=1}^{n}\sum\limits _{k=1}^{n}jk^{2}\phi (gcd(i,j,k))
=i=1∑n?j=1∑n?k=1∑n?jk2?(gcd(i,j,k))
= ∑ d = 1 n ? ( d ) ∑ i = 1 n ∑ j = 1 n ∑ k = 1 n j k 2 [ g c d ( i , j , k ) = d ] =\sum\limits _{d=1}^{n}\phi (d)\sum\limits _{i=1}^{n}\sum\limits _{j=1}^{n}\sum\limits _{k=1}^{n}jk^{2}[gcd(i,j,k)=d] =d=1∑n??(d)i=1∑n?j=1∑n?k=1∑n?jk2[gcd(i,j,k)=d]
= ∑ d = 1 n ? ( d ) d 3 ∑ i = 1 ? n d ? ∑ j = 1 ? n d ? ∑ k = 1 ? n d ? j k 2 [ g c d ( i , j , k ) = 1 ] =\sum\limits _{d=1}^{n}\phi (d) d^{3}\sum\limits _{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum\limits _{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum\limits _{k=1}^{\left \lfloor \frac{n}{d} \right \rfloor}j k^{2}[gcd(i,j,k)=1] =d=1∑n??(d)d3i=1∑?dn???j=1∑?dn???k=1∑?dn???j
