Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024

    为方便叙述设质数集合为P，所求答案为A，则

      (1)

      这里先处理这样一个问题：就是求出1≤x≤N，1≤y≤M，x与y互质的对数，记这个答案为B，则

      (2)

这里μ(x)是莫比乌斯函数。

//Ps:: 关于这个问题的解释：

由(2)可化(1)为

(3)

记T=pd，那么(3)式可化为

(4)

记(5)

那么对于一个质数p，我们可以推得

(6)

以上可以用欧拉筛法求μ(x)和g(x)，同时预处理出质数，然后就是把T分成O(sqrt(N))分来处理即可。