Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

题解

同bzoj1101

区间加减

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6  7 #define N 50007 8 using namespace std; 9 inline int read()10 {11     int x=0,f=1;char ch=getchar();12     while(ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();}13     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}14     return x*f;15 }16 17 int n,m,T;18 int tot,pri[N],mu[N],sum[N];19 bool flag[N];20 21 void init_mu()22 {23     mu[1]=1;24     for (int i=2;i<=50000;i++)25     {26         if (!flag[i]) pri[++tot]=i,mu[i]=-1;27         for (int j=1;j<=tot&&pri[j]*i<=50000;j++)28         {29             flag[pri[j]*i]=1;30             if (i%pri[j]==0){mu[i*pri[j]]=0;break;}31             else mu[i*pri[j]]=-mu[i];32         }33     }34     for (int i=1;i<=50000;i++)35         sum[i]=sum[i-1]+mu[i];36 }37 int solve(int n,int m)38 {39     if (n>m) swap(n,m);40     int ans=0,ps;41     for (int i=1;i<=n;i=ps+1)42     {    43         ps=min(n/(n/i),m/(m/i));44         ans+=(sum[ps]-sum[i-1])*(n/i)*(m/i);45     }46     return ans;47 }48 int main()49 {50     init_mu();51     T=read();52     while(T--)53     {54         int a=read(),b=read(),c=read(),d=read(),k=read();55         a=(a-1)/k,b=b/k,c=(c-1)/k,d=d/k;    56         printf("%d\n",solve(b,d)+solve(a,c)-solve(a,d)-solve(c,b));57     }58 }