一个想法就是先枚举最大公因数 ,而且可以肯定 是不可能太大的,最多是在 级别,看起来很靠谱!那么 可以写成这样(为了方便,我把质因子分解都写成 这样的形式)
现在看到一个非常不舒服的一项就是那个 ,因为这样一个条件表达式根本没法化简,但是我们可以用莫比乌斯反演把它替换
注意到这时候对于 来说唯一的限制就是它要不大于 ,那么我们令 就可以得到
现在有两种计算方法,一种是上面文章提到的 的方法,另一种是直接暴力快速幂计算
我们发现,当 很大的时候 是很小的,因此这时候暴力就好了,如果 很大的话, 就会变得很小,这时候就可以用平方的方法计算
现在问题就剩下一个了,如何预处理 的开方,答案是直接二分,但是你需要不断地优化常数