-
题意
给定(n,m(1 leqslant n,m leqslant 10000000)),求(1leqslant x leqslant n), (1 leqslant y leqslant m)且(gcd(x, y))为质数的((x, y))有多少对.
(T(leqslant 10000))组询问 -
题解
[ans = sum_{p in P}sum_{i=1}^{n}sum_{j=1}^{m}{[gcd(i,j)=p]} \
= sum_{p in P}sum_{i=1}^{lfloorfrac{n}{p}
floor}sum_{j=1}^{lfloorfrac{m}{p}
floor}{[gcd(i,j)=1]} \
= sum_{p in P}sum_{i=1}^{lfloorfrac{n}{p}
floor}sum_{j=1}^{lfloorfrac{m}{p}
floor}sum_{d|gcd(i,j)}mu(d) \
= sum_{p in P}sum_{i=1}^{lfloorfrac{n}{p}
floor}sum_{j=1}^{lfloorfrac{m}{p}
floor}sum_{d|i,d|j}mu(d) \
= sum_{p in P} sum_{d=1}^{min(n,m)} mu(d)iggllfloorfrac{n}{pd}iggr
floor iggllfloorfrac{m}{pd}iggr
floor \
= sum_{T}^{min(n,m)}iggllfloorfrac{n}{T}iggr
floor iggllfloorfrac{m}{T}iggr
floor sum_{p in P, p|T}mu(frac{T}{p})]
令$$f(T)=sum_{p in P, p|T}mu(frac{T}{p})$$
那么对(f(T))求前缀和则问题可以在(O(sqrt{n}))的时间内解决。
显然(f(T))可以通过类似埃式筛法在(O(nloglog n))的时间内求出
至此，问题在(O(nloglog n+Tsqrt{n}))内解决
————————————————————————————————————————
然而(f(T))仍然可以通过线性筛得到：
现在已知(f(x) = sum_{p'|x}mu(frac{x}{p'}))
考虑(f(px))
若(p|x)，则$$f(px) = sum_{p'|x}mu(frac{xp}{p'})$$
显然，当(p=p')时值为(mu(x))，当(p
e p')时，值为0.
所以此时(f(px) = mu(x))
若(p
ot|x)，则$$f(px) = sum_{p'|x}mu(frac{xp}{p'}) + mu(x) = -f(x) + mu(x)$$
至此，问题在(O(n+Tsqrt{n}))内解决