其实这道题目是莫比乌斯反演的入门题目，whatever，我们可以不从莫比乌斯反演的角度理解
由于这道题目\(a,b\)的值可以不同，所以不用数论容斥，换一个角度，考虑把\(k\)除进去然后互质
所以主要就是解释一下\(F[a,b]\)是怎么推导的
我们从容斥原理的角度考虑。对于任意一个二元组\((x,y)\)，如果\(gcd(x,y)≠1\)，那么\(gcd(x,y)\)一定是某一个质数的倍数
设\(P_i\)表示最大公约数的质数\(i\)的倍数的集合，那么我们要求的反面就是\(|P_2∪P_3∪P_5...|\)，将这个式子用容斥原理打开即可
然后我们震惊的发现，这个完全可以用莫比乌斯函数来描述。比如求\(|P_2∩P_3∩P_5|\)，就是求\(2\times3\times5=30\)的倍数的个数，其质因子的指数都为\(1\)（也就是所说的square-free number），所以莫比乌斯函数的值也就为\(±1\)，而且符号刚好与容斥中的符号相符；至于对于莫比乌斯函数值为\(0\)的数，此时就是某个质因子的指数大于\(1\)了，刚好我们写成这种形式不会影响答案
所以以上模型可以记住
最后讲一下那个优化
由于\(a\)最多贡献\(O(\sqrt{a})\)个不同的值，\(b\)最多贡献\(O(\sqrt{b})\)个不同的值，所以两者放一起就是最多贡献\(O(\sqrt{a}+\sqrt{b})\)个值；像代码那么写的话，每一次一定会跳到某一个段的右端点，也就是\(a\)或者\(b\)贡献的不同值，所以最多也只会跳根号次
标签：题目,所以,乌斯,sqrt,破译,密码,莫比,就是 From： https://www.cnblogs.com/dingxingdi/p/18171704