whj什么都不会系列-1

退役了只有一直没怎么做题,感觉水平退步了不少,以前一些比较显然的思路现在可能都想不到了. 这样下去肯定是不行的,我尽量时不时做点题写点题解恢复一点智商吧.

题意

给定\(n,m\),求有多少对\((i,j)\)满足\(1\le i\le n,1\le j\le m\)\(\gcd(i,j)\)为素数.

\(T\)组数据.

\(n\le 10^7,T\le 10^4\)

\(f(n,m)=\sum _{i=1}^n\sum _{j=1}^m[i\perp j]\),显然答案就是

\[\sum _{p\text{ is prime}}f([n/p],[m/p])\]

下面看\(f\)怎么算. 如果\(n=m\),显然有\(f(n,n)=\sum _{i=1}^n\varphi(n)\),预处理欧拉函数前缀和就可以做了.

\(n\neq m\)的时候一个显然的套路就是莫比乌斯反演:

\[\begin{aligned} f(n,m)=&\sum _{i}\sum _{j}\sum _{d|\gcd(i,j)}\mu(d)\\ =&\sum _{d}\mu(d) [n/d] [m/d] \end{aligned}\]

用整除分块可以做到\(\mathcal O(\sqrt{n})\)的复杂度,从而每次询问是\(\mathcal O(n^{3/4})\), 但这还是太慢了.

前面都是废话.

\(f\)本身的计算已经没什么办法优化了,考虑代入\(f([n/p],[m/p])\),得到

\[\begin{aligned} \sum _{p\text{ is prime}}f([n/p],[m/p])=&\sum _{p\text{ is prime}}\sum\mu(d) [n/(pd)] [m/(pd)]\\ =&\sum _{T}[n/T] [m/T]\sum _{p|T,p\text{ is prime}}\mu(T/p) \end{aligned}\]

\(g(T)=\sum _{p|T,p\text{ is prime}}\mu(T/p)\),观察一下可以发现\(g(n)\)很有规律.

\(s _1(n),s _2(n)\)分别为\(n\)的不同素因数个数和歌素因数的指数和,那么当\(s _1(n)=s _2(n)\)时,\(g(T)=-s _1(n)(-1)^{s _1(n)}\),当\(s _1(n)+1=s _2(n)\)时,\(g(T)=(-1)^{s _1(n)}\),当\(s _1(n)+2\le s _2(n)\)时,\(g(T)=0\).

于是就可以很容易地处理\(g(n)\)的前缀和,进而\(\mathcal O(\sqrt{n})\)地处理每次询问.