因为这里的a和c不一定为1,所以我们要使用容斥
并且因为询问组数较多，我们每次不能线性的使用莫比乌斯反演，我们要对区间进行分块
分块其实很简单,具体看代码吧
我的代码：
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int maxn=50000+100;int mu[maxn],sum[maxn];
bool isprime[maxn];
int prime[maxn],tot;void init(){for(int i=0;i<maxn;i++) isprime[i]=true;isprime[0]=isprime[1]=false;tot=0;sum[0]=0;sum[1]=mu[1]=1;for(int i=2;i<maxn;i++){if(isprime[i]) prime[tot++]=i,mu[i]=-1;for(int j=0;j<tot && i*prime[j]<maxn;j++){isprime[i*prime[j]]=false;if(i%prime[j]) mu[i*prime[j]]=-mu[i];else break;}}for(int i=2;i<maxn;i++) sum[i]=sum[i-1]+mu[i];
}ll Mobius(int a,int b){if(a>b) swap(a,b);int pos;ll res=0;for(int i=1;i<=a;i=pos+1){pos=min(a/(a/i),b/(b/i));res+=(ll)(sum[pos]-sum[i-1])*(a/i)*(b/i);}return res;
}int main(){int n;scanf("%d",&n);init();while(n--){int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);a--,c--; a/=k;b/=k;c/=k;d/=k;printf("%lld\n",Mobius(b,d)-Mobius(a,d)-Mobius(b,c)+Mobius(a,c)); }}