題目大意：給定兩個(gè)區(qū)間，[a,b] [c,d] 設(shè)x屬于第一個(gè)區(qū)間，y屬于第二個(gè)區(qū)間，求gcd(x,y)=k的實(shí)數(shù)對(duì)有多少個(gè)。
方法：對(duì)兩個(gè)區(qū)間分別除以k，轉(zhuǎn)化為求新區(qū)間內(nèi)，互質(zhì)的實(shí)數(shù)對(duì)有多少個(gè)。
容斥原理：|t1Ut2U...Utn| = sum[ti] - sum[ti n tj] + sum[ti n tj n tk] - ... + (-1)^(m+1)|t1 n t2 n ... n tn|
把所有有是1的倍數(shù)的點(diǎn)對(duì)加起來(lái)  減去既有1也有（2，3，5。。。）的點(diǎn)對(duì)   加上既有1也有2也有3.。的點(diǎn)對(duì)


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

bool mark[100010];
int prim[10000], tot =0, sum = 0;
struct node{
     int v; //v存的是數(shù)  就是乘積  k是記錄減還是加
     int k;
}tb[70000];

void di(long long p,int k,int odd) {//奇數(shù)個(gè)因數(shù)的就加 偶數(shù)個(gè)因數(shù)的就減
     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;    
}