题目大意：给定两个区间，[a,b] [c,d] 设x属于第一个区间，y属于第二个区间，求gcd(x,y)=k的实数对有多少个。
方法：对两个区间分别除以k，转化为求新区间内，互质的实数对有多少个。
容斥原理：|t1Ut2U...Utn| = sum[ti] - sum[ti n tj] + sum[ti n tj n tk] - ... + (-1)^(m+1)|t1 n t2 n ... n tn|
把所有有是1的倍数的点对加起来  减去既有1也有（2，3，5。。。）的点对   加上既有1也有2也有3.。的点对


#include <stdio.h>
#include <algorithm>
using namespace std;

bool mark[100010];
int prim[10000], tot =0, sum = 0;
struct node{
     int v; //v存的是数  就是乘积  k是记录减还是加
     int k;
}tb[70000];

void di(long long p,int k,int odd) {//奇数个因数的就加 偶数个因数的就减
     if (k == tot) return;
     long long tmp = p*prim[k]; 
     if (tmp > 100000) return;
     di(p,k+1,odd);
     tb[sum].v = tmp;
     tb[sum++].k = -odd;
     di(tmp,k+1,-odd);
}

void swap(int &a,int &b) {
     a += b;
     b = a-b;
     a = a-b;
}

int cmp(node a,node b) {
    return a.v < b.v;
}

int main () {
    int i, j;
    for (i = 2; i <= 100000; i++) {
        if (!mark[i]) {
           prim[tot++] = i;
           for (j = i+i; j <= 100000; j += i)
               mark[j] = 1;
        }
    }
    tb[0].v = 1; tb[0].k = 1;
    sum = 1;
    di(1,0,1);
    sort(tb,tb+sum,cmp);
    int kase, a, b, c, d, k, o = 1;
    scanf("%d", &kase);
    while (kase--) {
          scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
          if (k == 0) {
             printf("Case %d: 0\n", o++);
             continue;
          }
          int x = b/k;
          int y = d/k;
          if (x == 0 || y == 0) {
             printf("Case %d: 0\n", o++);
             continue;
          }
          if (x > y) swap(x,y);
          long long ans = 0;
          for (i = 0; i < sum; i++) {
              if (x < tb[i].v) break;
              long long tmpx = x/tb[i].v;
              long long tmpy = y/tb[i].v;
              long long c = tmpx*tmpy-(tmpx-1)*tmpx/2;
              ans += c*tb[i].k;
          }
          printf("Case %d: %I64d\n",o++,ans);
    }
    return 0;    
}