对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

这里题目意思很明显

对于要求的f[n] = sigma (a≤x≤b) sigma(c≤y≤d) [gcd(x,y)=k] =  sigma (1≤x≤b) sigma(1≤y≤d) [gcd(x,y)=k] + sigma (1≤x≤a-1) sigma(1≤y≤c-1) [gcd(x,y)=k] - sigma (1≤x≤a-1) sigma(1≤y≤d) [gcd(x,y)=k] -  sigma (1≤x≤b) sigma(1≤y≤c-1) [gcd(x,y)=k] 

对于每一个g[n] = sigma(1≤x≤a) sigma(1≤y≤c) [gcd(x,y)=k] = sigma(1≤x≤a/k) sigma(1≤y≤c/k) [gcd(x,y)=1] = sigma(1≤x≤a/k) sigma(1≤y≤c/k) sigma(d|gcd(x,y)) mu[d] = sigma(d) mu[d]*a/k/d*c/k/d

 

a/k/d*c/k/d 这一段区间相等的部分可以加在一起算，得到当前一样值的结束是 min(x/(x/i) , y/(y/i)) 

记录莫比乌斯函数的前缀和就可以整段区间更新，这样循环就缩小到了sqrt(n)的复杂度

1 #include 
     
       2 using namespace std; 3 #define ll long long 4 #define N 50000 5 int mu[N+10] , prime[N+10] , tot , sum[N+10]; 6 bool check[N+10]; 7  8 void get_mu() 9 {10     mu[1] = 1;11     for(int i=2 ; i<=N ; i++){12         if(!check[i]){13             prime[tot++] = i;14             mu[i] = -1;15         }16         for(int j=0 ; j
      
       N) break;18             check[i*prime[j]] = true;19             if(i%prime[j]){20                 mu[i*prime[j]] = -mu[i];21             }else break;22         }23     }24     for(int i=1 ; i<=N ; i++) sum[i]=sum[i-1]+mu[i];25 }26 27 int a,b,c,d,k;28 29 int solve(int x , int y)30 {31     x/=k , y/=k;32     int mx = min(x , y) , len , ret=0;33     for(int i=1 ; i<=mx ; i=len+1)34     {35        // cout<
       <<" "<
        
         <