警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P2568」GCD - 莫比乌斯反演

题意

传送门:洛谷 P2568 - GCD

单次询问,给 \(n\),求 \(x, y \in [1, n]\)\(\gcd(x, y)\) 为质数的 \((x, y)\) 二元组数。

解法

推式子。 \[ \begin{aligned} & \begin{aligned} ans & = \sum_{k\in P}\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=k] \\ & = \sum_{k\in P}\sum_{i=1}^{\!\left\lfloor\!\frac nk\!\right\rfloor\!}\sum_{j=1}^{\!\left\lfloor\!\frac mk\!\right\rfloor\!}[\gcd(i,j)=1] \\ & = \sum_{k\in P}\left[-1+\sum_{i=1}^{\!\left\lfloor\!\frac nk\!\right\rfloor\!}\left(2\sum_{j=1}^i[\gcd(i,j)=1]\right)\right] \\ & = \sum_{k\in P}\left(-1+\sum_{i=1}^{\!\left\lfloor\!\frac nk\!\right\rfloor\!}2\cdot\varphi(i)\right) \\ \end{aligned} \end{aligned} \]

然后筛出 \(\varphi\) 就做完了。

代码