BZOJ2820 - YY的GCD

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$可知每个素数的均摊更新次数是$logN$的。

  又由素数定理可得$N$以内大概有$\frac{N}{logN}$个质数。因此预处理的时间复杂度为$O(N)$级别的。

  总时间为$O(N+T \sqrt N)$

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang