P1587[NOI2016]循环之美

emmmmm

这是一道莫比乌斯反演+杜教筛的好题

题目就不赘述了，即求： \[ \sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k] \] 这个看完题应该就知道怎么证明了

好，继续化简式子:

\(Step\;One:\) \[ \begin{align*} &\quad\sum_{j=1}^m[j\perp k]\sum_{i=1}^n[i\perp j]\\ &=\sum_{j=1}^m[j\perp k]\sum_{i=1}^n\sum_{d|\gcd(i,j)}\mu(d)\\ &=\sum_{d=1}^{\min(n, m)}\frac nd\mu(d)\sum_{j=1}^{\frac md}[jd\perp k]\\ &=\sum_{d=1}^{\min(n, m)}\frac nd\mu(d)[d\perp k]\sum_{j=1}^{\frac md}[j\perp k] \end{align*} \] \(Step\;Two:\)

考虑拆分\(\sum\limits_{j=1}^{\frac md}[j\perp k]\)

你可以莫比乌斯反演，但是那样就太麻烦了，这个我们可以考虑用欧拉函数和剩余系的方法来处理，于是有： \[ f(n)=\frac nk\varphi(k)+f(n\%k) \] 这个可以预处理+度教筛

\(Step\;Three:\)

考虑 \[ \begin{align*} g(n,k)&=\sum_{d=1}^n\mu(d)[d\perp k]\\ &=\sum_{d=1}^n\mu(d)\sum_{d\prime|(d,k)}\mu(d\prime)\\ &=\sum_{d=1}^n\mu(d)\sum_{d\prime|d,d\prime |k}\mu(d\prime)\\ &=\sum_{d\prime=1}^n... \end{align*} \] 先说下一种的

考虑先处理\([j\perp k]\)，化简可以得到 \[ \begin{align*} f(n,m,k)&=\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]\\ &=\sum_{d|k}\mu(d)f(\frac md,n,d) \end{align*} \] 边界就不用说了？

看代码

​