P8570 [JRKSJ R6] 牵连的世界
orz_z
·
·
个人记录
P8570 [JRKSJ R6] 牵连的世界
应该知道的，σ_0(ij)=\sum\limits_{d|\gcd(i,j)}\mu(d)σ_0(\frac{i}{d})σ_0(\frac{j}{d})，\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}。
\begin{aligned}
\sum_{i=1}^{n}\sum_{j=1}^{m}σ_0(ij)\varphi(ij)
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{t}\frac{\varphi(i)\varphi(j)t}{\varphi(t)}[\gcd(i,j)=t]\sum_{d|t}\mu(d)σ_0(\frac{i}{d})σ_0(\frac{j}{d})\\
&=\sum_{t}\sum_{d|t}\frac{\mu(d)t}{\varphi(t)}\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}[\gcd(i,j)=1]\varphi(it)\varphi(jt)σ_0(\frac{it}{d})σ_0(\frac{jt}{d})\\
&=\sum_{T}\left(\sum_{t|T} \frac{t}{\varphi(t)}\cdot\mu(\frac{T}{t})\right)\left(\sum_{d|T}\mu(d)\left(\sum_{T|i}^{\lfloor\frac{n}{d}\rfloor}\varphi(id)σ_0(i)\right)\left(\sum_{T|i}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)σ_0(i)\right)\right)
\end{aligned}
拿个高维前缀和狄利克雷优化，可做到 \mathcal O(n\log n \log \log n)。
代码gugu.