就在例题的基础上加个容斥。注意循环部分不要开long long ，时间会极大幅度的增长。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long ll;
int vis[maxn];
int pri[maxn],mu[maxn],sum[maxn],cnt;
void getMu (ll n) {
mu[1]=1;
for (ll i=2;i<=n;i++) {
if (!vis[i]) {
mu[i]=-1;
pri[++cnt]=i;
}
for (ll j=1;j<=cnt&&i*pri[j]<=n;j++) {
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
else mu[i*pri[j]]=-mu[i];
}
}
for (ll i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
int solve (int a,int b,int d) {
if (a>b) swap(a,b);
int ans=0;
for (ll l=1,r;l<=a;l=r+1) {
r=min(a/(a/l),b/(b/l));
ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
}
return ans;
}
main () {
int _;
scanf("%d",&_);
getMu(60000);
while (_--) {
int a,b,c,d,e;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
int ans=solve(b,d,e)-solve(b,c-1,e)-solve(a-1,d,e)+solve(a-1,c-1,e);
printf("%lld\n",ans);
}
}