NowCoder 8282 D(莫反)
很久没写提解，也没打比赛了，昨天做了个题
题目
https://ac.nowcoder.com/acm/contest/8282/D
题解
https://blog.nowcoder.net/n/aa0719c9f7d9481cb0f9f93eb5e8a866
收获
关于莫反之前写过文章了，也很容易可以预先处理所有mu[1~n]
这次根据题目总结一下莫反的思路吧。
和上次类似，其实核心两点
- 找到 $gcd(x,y) == 1$这样对应的表达式
- 这样的表达式意味着我们可以用 $\sum_{i|gcd(x,y)}{\mu(i)} = [gcd(x,y)==1]$的知识
- 变成了 多层求和公式以后，注意求和的约数遍历值，逐个相邻的求和向前移动这个约数遍历值
- 最后就能得到完全没有约数只有倍数的 求和式子，可以各种前缀和之类的处理了