hdu1695 GCD2 容斥原理 求x属于[1,b]与y属于[1,d]，gcd(x,y)=k的对数。(5,7)与(7,5)看作同一对。

GCD

Time Limit: / MS (Java/Others)    Memory Limit: / K (Java/Others)

Total Submission(s):     Accepted Submission(s):

Problem Description

Given  integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.

Please notice that, (x=, y=) and (x=, y=) are considered to be the same.

Yoiu can assume that a = c =  in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than , cases.

Each case contains five integers: a, b, c, d, k,  < a <= b <= ,,  < c <= d <= ,,  <= k <= ,, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

Sample Output

Case :

Case :

Hint

For the first sample input, all the  pairs of numbers are (, ), (, ), (, ), (, ), (, ), (, ), (, ), (, ), (, ).

/**

题目：hdu1695 GCD2

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695

题意：求x属于[1,b]与y属于[1,d]，gcd(x,y)=k的对数。(5,7)与(7,5)看作同一对。

思路：

gcd(x,y)=k => gcd(x/k,y/k) = 1;

则求x/k与y/k互质对数。

即求：[1,b/k]与[1,d/k]之间互质的对数

设x属于[1,b/k], y属于[1,d/k];

枚举x，求x与y互质的对数。所以要预处理所有x的质因子。然后容斥处理。由于(x,y)=>(5,7),(7,5)是同一组。

所以：答案为ans += (d/k) - x在d/k中不互质的数 - (x-1);

*/

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<map>

#include<set>

#include<cmath>

#include<queue>

#define LL long long

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e5+;

vector<int> prime[maxn];

int flag[maxn];

void init()

{

    memset(flag, , sizeof flag);

    for(ll i = ; i < maxn; i++){

        if(flag[i]==){

            prime[i].push_back(i);

            for(ll j = *i; j < maxn; j+=i){

                prime[j].push_back(i);

                flag[j] = ;

            }

        }

    }

}

ll rc(int pos,int n)

{

    ll sum = ;

    ll mult, ones;

    ll len = prime[pos].size();

    ll m = <<len;

    for(int i = ; i < m; i++){

        ones = ;

        mult = ;

        for(int j = ; j < len; j++){

            if(i&(<<j)){

                ones++;

                mult = mult*prime[pos][j];

                if(mult>n) break;

            }

        }

        if(ones%==){

            sum -= n/mult-(pos-)/mult;

        }else

        {

            sum += n/mult-(pos-)/mult;

        }

    }

    return n-(pos-)-sum;

}

int main()

{

    init();

    int T;

    int cas = ;

    int a, b, c, d, k;

    cin>>T;

    while(T--)

    {

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

        if(k==){

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

        }

        if(b>d) swap(b,d);///for b<=d;

        b = b/k;

        d = d/k;

        ll ans = ;

        if(b>=){

            ans += d;

        }

        for(int i = ; i <= b; i++){

            ans += rc(i,d);

        }

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

    }

    return ;

}