Solution
由数论基础知识 答案即为$$\sum_{i = 1}^n\sum_{j = 1}^m[i \perp j][j \perp k]$$
莫反套路可化为$$\sum_{d = 1}\mu(d)[d \perp k] \lfloor \frac{n}{d} \rfloor \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[j \perp k]$$
如果我们可以求出\(g(x)=\sum_{i=1}^x [x \perp k]\)，那么后面那坨东西就容易分块搞掉
然后我们惊奇的发现\(g(n)=\lfloor \frac{n}{k} \rfloor g(k) + g(n\mod k)\)
然后我们只需要求\(f(n)=\sum_{i=1}^n \mu(i)[i \perp k]\)的前缀和了
这一部分是本题难点。
发现
\[\begin{aligned}
f(n)&=\sum_{i=1}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] \\
&=\sum_{i=1}^n \sum_{j=1}^{\lfloor \frac{n}{i} \rfloor} \mu(j) [ij \perp k] - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k]\\
&=\sum_{T=1}^n [T \perp k] \sum_{d | k}\mu(d) - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] \\
&=1 - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k]
\end{aligned}
\]
至此，我们成功构造出了杜教筛式子。
问题迎刃而解。
Code
#include
#include
#include