思路：

同BZOJ1101 就是加个容斥 …

http://blog.csdn.net/qq_31785871/article/details/54340241

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 50001

int prime[N],mu[N],vis[N],sum[N],tot;

int a,b,c,d,k,n,ans,pos;

int solve(int x,int y){

    int temp=min(x,y),jy=0;

    for(int i=1;i<=temp;i=pos+1){

        pos=min(x/(x/i),y/(y/i));

        jy+=(sum[pos]-sum[i-1])*(x/i)*(y/i);

    }return jy;

}

int main(){

    sum[1]=1;

    for(int i=2;i<N;i++){

        if(!vis[i])prime[++tot]=i,mu[i]=-1;

        for(int j=1;j<=tot&&i*prime[j]<N;j++){

            vis[i*prime[j]]=1,mu[i*prime[j]]=-mu[i];

            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}

        }

        sum[i]=sum[i-1]+mu[i];

    }

    scanf("%d",&n);

    while(n--){

        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

        printf("%d\n",solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)+solve((a-1)/k,(c-1)/k));

    }

}