题解：P8570 [JRKSJ R6] 牵连的世界
lovely_nst
·
·
题解
\sum_{i=1}^n\sum_{j=1}^mc(ij)\varphi(ij)\\
=\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\sum_{x|i}\sum_{y|i}[\gcd(x,y)=1]\\
=\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\sum_{x|i}\sum_{y|i}\sum_{d|x,d|y}\mu(d)\\
=\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\sum_{d=1}c(\frac id)c(\frac jd)\mu(d)\\
=\sum_{d=1}\mu(d)\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}\frac{\varphi(id)\varphi(jd)\gcd(i,j)d}{\varphi(\gcd(i,j)d)}c(i)c(j)\\
=\sum_{d=1}\mu(d)d\sum_{k=1}\sum_{i=1}^{\frac n{dk}}\sum_{j=1}^{\frac m{dk}}\frac{\varphi(idk)\varphi(jdk)[\gcd(i,j)=1]k}{\varphi(kd)}c(ik)c(jk)\\
=\sum_{d=1}\mu(d)d\sum_{k=1}\frac k{\varphi(kd)}\sum_{i=1}^{\frac n{dk}}\varphi(idk)c(ik)\sum_{j=1}^{\frac m{dk}}\varphi(jdk)c(jk)\sum_{w|i,w|j}\mu(w)\\
=\sum_{d=1}\mu(d)d\sum_{k=1}\frac k{\varphi(kd)}\sum_{w=1}\mu(w)\sum_{i=1}^{\frac n{dkw}}\varphi(idkw)c(ikw)\sum_{j=1}^{\frac m{dkw}}\varphi(jdkw)c(jkw)\\