# 「NOI 2016」循环之美-莫比乌斯反演 + 杜教筛

### 题解

\begin{aligned} x \cdot k ^ l &\equiv x \ (\text{mod } y)\\ k ^ l &\equiv 1 \ (\text{mod } y) \end{aligned}

\begin{aligned}&\sum_{x=1}^{n} \sum_{y=1}^{m}[x\perp y][y \perp k]\\=&\sum_{y=1}^{m}[y\perp k]\sum_{x=1}^{n}[x\perp y]\\ =& \sum_{y = 1} ^ m[y \perp k]\sum_{x = 1} ^ n[\gcd(x, y) = 1]\end{aligned}

\begin{aligned}\sum_{y = 1} ^ m[y \perp k]\sum_{d | y} ^ n\mu(d)\lfloor \frac n d \rfloor \end{aligned}

\begin{aligned}&\sum_{d=1}^{n}\mu(d)\lfloor \frac{n}{d} \rfloor \sum_{y=1}^{m}[d\ |\ y][y\perp k]\\=&\sum_{d=1}^{n}\mu(d)\lfloor \frac{n}{d}\rfloor \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor}[id\perp k]\\=& \sum_{d=1}^{n}[d\perp k]\mu(d)\lfloor \frac{n}{d}\rfloor \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor}[i\perp k]\end{aligned}

$$f(n, k) = \sum_{i = 1} ^ n[i \perp k]$$

$$[a \perp b] = [a \text{ mod }b \perp b]$$

$$f(n, k) = \lfloor \frac n k \rfloor f(k, k) + f(n \text{ mod } k, k)$$

$$g(n, k) = \sum_{i = 1} ^ n [i \perp k]\mu(i)$$

\begin{aligned}g(n,k)&=\sum_{i=1}^n[i\perp q]\mu(i)-\sum_{y=1}^{\lfloor\frac{n}{p}\rfloor}[py\perp q]\mu(py) \\&=g(n,q)- \sum_{y=1}^{\lfloor\frac{n}{p}\rfloor}[y\perp q]\mu(py)\end{aligned}

\begin{aligned}g(n,k)&=g(n,q)- \sum_{y=1}^{\lfloor\frac{n}{p}\rfloor}[y\perp p][y\perp q]\mu(p)\mu(y)\\&=g(n,q)-\mu(p)\sum_{y=1}^{\lfloor\frac{n}{p}\rfloor}[y\perp k]\mu(y)\\&=g(n,q)+g(\lfloor\frac{n}{p}\rfloor,k) \end{aligned}

# Math