2019ICPC南昌邀请赛网络赛 G.tsy's number （数论） 积性函数+容斥
2019ICPC南昌邀请赛网络赛 G.tsy's number
题意
求(sum_{i=1}^nsum_{j=1}^nsum_{k=1}^nfrac{phi(i)phi(j^2)phi(k^3)}{phi(i)phi(j)phi(k)}phi(gcd(i,j,k)))
共T组数据，(Tleq 10000)，(1leq n leq 10^7)
题解
枚举gcd(i,j,k) = d，然后容斥一下
[egin{align*}
ans
&= sum_{d=1}^nphi(d)sum_{i=1}^{[frac{n}{d}]}sum_{j=1}^{[frac{n}{d}]}sum_{k=1}^{[frac{n}{d}]} [gcd(i,j,k)==1]frac{phi(i*d)phi((j*d)^2)phi((k*d)^3)}{phi(i*d)phi(j*d)phi(k*d)}\
&= sum_{d=1}^nphi(d)sum_{s=1}^{[frac{n}{d}]}mu(s)sum_{i=1}^{[frac{n}{d*s}]}sum_{j=1}^{[frac{n}{d*s}]}sum_{k=1}^{[frac{n}{d*s}]} frac{phi(i*d*s)phi((j*d*s)^2)phi((k*d*s)^3)}{phi(i*d*s)phi(j*d*s)phi(k*d*s)}\
&= sum_{d=1}^nphi(d)sum_{s=1}^{[frac{n}{d}]}mu(s)sum_{i=1}^{[frac{n}{d*s}]}frac{phi(i*d*s)}{phi(i*d*s)}sum_{j=1}^{[frac{n}{d*s}]}frac{phi((j*d*s)^2))}{phi(j*d*s)} sum_{k=1}^{[frac{n}{d*s}]}frac{phi((k*d*s)^3)}{phi(k*d*s)}\
end{align*}
]
可以归纳证明，
[sum_{i=1}^{[frac{n}{d}]}frac{phi((i*d)^k)}{phi(i*d)} = d^{(k-1)}* sum_{i=1}^{[frac{n}{d}]}i^{(k-1)}
]
所以
[egin{align*}
ans
&= sum_{d=1}^nphi(d)sum_{s=1}^{[frac{n}{d}]}mu(s)* (d*s)^3*[frac{n}{d*s}]* sum_{i=1}^{[frac{n}{d*s}]}i* sum_{i=1}^{[frac{n}{d*s}]}i^2
end{align*}
]
设(T=s*d),则
[egin{align*}
ans
&= sum_{T=1}^n (T^3* [frac{n}{T}]* sum_{i=1}^{[frac{n}{T}]}i* sum_{i=1}^{[frac{n}{T}]}i^2)* sum_{d|T}phi(d)* mu(T/d)
end{align*}
]
前面一部分和它的前缀和显然可以预处理，后面是两个积性函数的狄利克雷卷积，设为f(T)，p为与T互质的质数，则有
[egin{align*}
f(p^k*T)
&= sum_{i=0}^ksum_{d|T}phi(p^i*d)* mu(frac{p^{k-i}* T}{d})\
&= (phi(p^k)-phi(p^{k-1}))* f(T)
end{align*}
]
可以用线性筛预处理，然后就是(sqrt n)的套路了，总复杂度为(O(n+T*sqrt n)).