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