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})$地处理每次询问.