题目大意：给你 a , b , c , d , k 五个值 （题目说明了 你可以认为 a=c=1）  x 属于 [1,b] ，y属于[1,d]  让你求有多少对这样的 （x,y）满足gcd（x,y）==k。给你的时间是 3000 MS。   0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000

解题思路：因为  gcd（x,y）=k  那么，很显然 gcd（x / k,y / k）是等于 1 的（x,y 除了 k 一定没有其他的公因数）。那么，此时问题就可以转化为： x 属于 [1,b / k] ，y属于[1,d / k]  让你求有多少对这样的 （x,y）满足gcd（x,y）== 1 即x和y是互质的。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100000;

//线性筛法求莫比乌斯函数

bool check[MAXN+10];

int prime[MAXN+10];

int mu[MAXN+10];

//递推

void mobius(ll mn)

{

    mu[1]=1;

    for(ll i=1;i<=mn;i++){

        for(ll j=i+i;j<=mn;j+=i){

            mu[j]-=mu[i];

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    int n,a,b,d,c,k,bd,Case=1;

    mobius(MAXN);

    cin>>n;

    while(n--)

    {

        cin>>a>>b>>c>>d>>k;

         if(k==0){

           printf("Case %d: 0\n",Case++);

            continue;

        }

        b=b/k;

        d=d/k;

        bd = min(b,d);

        ll ans1=0,ans2=0;

        for(int i=1;i<=bd;i++)

            ans1+=(ll)mu[i]*(b/i)*(d/i);

        for(int i=1;i<=bd;i++)

            ans2+=(ll)mu[i]*(bd/i)*(bd/i);

        ll ans = ans1-ans2/2;

        printf("Case %d: %lld\n",Case++,ans);

    }

    return 0;

}