题目大意：

一、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个约数；

二、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个倍数。

 

第一行两个数：p和q。（1<p<10^7 ，1<q<1000。）

接下来有q行，每行两个数A和B。（1<A,B<10^7）

 

我们先考虑第二个问题 ，很简单答案就是 (A/p) * (B/p) , 因为从p开始每次叠加p枚举到A，B中间得到的数都是可以任意选择，gcd()的值必然是p的倍数的

 

我们考虑第一个问题，这里约数的个数不超过数字n的2sqrt(n)个

所以我们可以枚举出每一个约数k,然后对k进行求和

对于使用莫比乌斯反演求和的话只是从当前来说复杂度大概是

O(q*lg(p)*(sqrt(A)+sqrt(B))  //sqrt(A)是因为对莫比乌斯数组求前缀和进行快速计算，这是莫比乌斯中常出现的方式

为了较低复杂度，我们列式计算考虑降维

如下列公式所示：

 

最后是如何计算sum[t],能计算出sum[]数组的话，t最大不超过min(A,B)那么总复杂度就能降为O(q*(sqrt(A)+sqrt(B))就没问题了

 

这里t只跟k,d有关系，那么只要枚举每一个k,d就能得到sum[t]的数组了

for(int i=0 ; i

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 #define ll long long 8 #define N 10005 9 #define M 1000000010 int p,q,a,b,cnt;11 int fac[N];12 int mu[M+5] , prime[M/10] , tot , sum[M];13 bool check[M+5];14 15 void get_mu()16 {17     mu[1] = 1;18     for(int i=2 ; i<=M ; i++){19         if(!check[i]){20             mu[i] = -1;21             prime[tot++] = i;22         }23         for(int j=0 ; j
         
          M) break;25             check[prime[j]*i] = true;26             if(i%prime[j]==0) break;27             else mu[i*prime[j]] = -mu[i];28         }29     }30 }31 32 void init()33 {34     int v = (int)sqrt(p+0.5);35     for(int i=1 ; i<=v ; i++){36         if(p%i==0){37             fac[cnt++] = i;38             if(p/i!=i) fac[cnt++] = p/i;39         }40     }41 }42 43 void pre_solve()44 {45     for(int i=0 ; i
          
           b) swap(a , b);72 printf("%lld %lld\n" , cal(a,b) , (ll)(a/p)*(b/p));73 }74 }