BZOJ2820 - Click Here
Description
神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种傻×必然不会了，于是向你来请教……多组输入
Input
第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Solution
BZOJ2301的加强版orz….
我们可以枚举一个质数$k$，然后答案为$\sum_k\sum_{a,b} [(a,b)=k]$
内层和式利用BZOJ2301的套路，莫比乌斯反演可得$\sum_k\sum_d \mu(d) \lfloor \frac{N}{kd} \rfloor \lfloor \frac{M}{kd} \rfloor$
利用分块优化我们就得到了$O(\frac{TN \sqrt N}{logN})$做法，稳稳的TLE….
考虑进一步优化。
注意到内层和式$kd$表示了$N$以内所有的数，因此设$T=kd$
则上式变为$\sum_T \lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{d} \mu(d)[\frac{T}{d} \, is \, prime]$
如果能够预处理出内层和式的前缀和，那么每次询问可在$O(\sqrt N)$内解决。
$\frac{T}{d}$是素数，表明$T$是素数的倍数。因此可以枚举素数，然后去更新每个素数的倍数，再统计前缀和。
至于时间复杂度，根据调和数$H_n$可知每个素数的均摊更新次数是$ln \,N$的。
又由素数定理可得$N$以内大概有$\frac{N}{ln \, N}$个质数。因此预处理的时间复杂度为$O(N)$级别的。
总时间为$O(N+T \sqrt N)$
CODE
CODE - Click Here