题面
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
首先将问题转化一下，不妨设f[x][y]表示1<=i<=x,1<=j<=y,且gcd(i,j) = k ,数对(i,j)的个数;
那么由容斥原理，原问题可转化为 f[b][d] - f[a-1][d] - f[b][c-1] + f[a-1][c-1];
现在来重点解决子问题，即f[x][y]，剩下的调用函数就好了;
再转化一下，gcd(x,y) = k ,其实就是 x/k 与 y/k 互质，那么问题就是求1<=i<=x/k , 1<=j<=y/k , 且gcd(i,j) = 1 的点对 (i,j) 的个数;
不妨设g[x][y][k]表示1<=i<=x , 1<=j<=y , k | gcd(i,j) 的点对个数 那么我们发现要满足此条件，只需让 k | i , k | j 即可，所以这样的点对的个数为 (x/k) * (y/k);
那么有什么用呢，继续容斥;
f[x][y]=Σ(i=1,i<=min(x,y) ) µ(i) * g[x][y][i] ;
其中µ为莫比乌斯函数。
怎样理解呢？ 当i=1时，相当于加上所有的点对，然后减去gcd(i,j) 是 2,3,5……等单个质数的倍数的点对的个数，
然后就会发现多减了是 2*3,2*5……等两个质数的乘积的倍数的点对，再加上，这样循环就能求出gcd(i,j) = 1的点对的个数啦；
至于那些质因子里面有两个相同质因子的数，比如12=2*2*3，在统计2*3时就已经算过了，所以就不再统计。
然后发现这样刚好满足莫比乌斯函数，直接线筛出莫比乌斯函数就好了；
最后就是加一个整除分块，即对于x、i ， i ~ x / ( x / i ) 的 i / k 都是相等的，对于此题就是min( x / ( x / k ） ，y / (y / k ) );
附上代码
#include<cstdio> #include<iostream> using namespace std; int n,k,miu[50010],sum[50010],ans; bool v[50010]; int solve(int a,int b){ a=a/k;b=b/k;ans=0; for(int l=1,r;l<=min(a,b);l=r+1){ r=min(a/(a/l),b/(b/l)); ans+=(sum[r]-sum[l-1])*(a/l)*(b/l); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=50000;i++) miu[i]=1; for(int i=2;i<=50000;i++){ if(v[i]) continue;miu[i]=-1; for(int j=i*2;j<=50000;j+=i) v[j]=1,miu[j]= (j/i)%i ? miu[j]*-1 : 0; } for(int i=1;i<=50000;i++) sum[i]=sum[i-1]+miu[i]; while(n--){ int a,b,c,d; scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%d ",solve(b,d)-solve(b,c-1)-solve(a-1,d)+solve(a-1,c-1)); } return 0; }