同[bzoj1101]Zap，容斥即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int t,a,b,c,d,k,f[50005],vis[100005],p[50005]; 4 void mobies(int n){ 5 memset(f,0,sizeof(f)); 6 f[1]=1; 7 for(int i=2;i<=n;i++){ 8 if (!vis[i])f[p[++p[0]]=i]=-1; 9 for(int j=1;j<=p[0];j++){ 10 vis[i*p[j]]=1; 11 if ((p[j]*i>n)||(i%p[j]==0))break; 12 f[i*p[j]]=-f[i]; 13 } 14 } 15 for(int i=2;i<=n;i++)f[i]+=f[i-1]; 16 } 17 int calc(int n,int m){ 18 int ans=0; 19 n/=k; 20 m/=k; 21 if (n>m)swap(n,m); 22 for(int i=1,j;i<=n;i=j+1){ 23 j=min(m/(m/i),n/(n/i)); 24 ans+=(f[j]-f[i-1])*(n/i)*(m/i); 25 } 26 return ans; 27 } 28 int main(){ 29 mobies(50000); 30 scanf("%d",&t); 31 while (t--){ 32 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 33 a--,c--; 34 printf("%d\n",calc(b,d)-calc(a,d)-calc(c,b)+calc(a,c)); 35 } 36 }