HDU - 1695 - GCD - （容斥定理，歐拉函數）

Given 5 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=5, y=7) and (x=7, y=5) are considered to be the same. 

Yoiu can assume that a = c = 1 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 3,000 cases. 

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

Output

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

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9
           

Sample Output

Case 1: 9
Case 2: 736427


        
  
           

Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
           

題意：給出a,b,c,d,k,求有多少對[x,y],其中x屬于[a,b]，y屬于[c,d]使得gcd(x,y)=k;且有a，c始終為1，（x，y）與（y，x）視為同一種情況。

那麼找gcd(x,y)=k，等于找gcd（x/k，y/k）=1；即從區間[1,b/k]與[1，d/k]中各取一個數，且這兩個數互質的情況，那麼這個問題可以轉換為求對于區間[1,d/k]中每個數，在區間[1,b/k]中有多少個數與其互質，最後再求和。

1.對于區間[1,d/k]中小于b/k的數，他們在區間[1,b/k]中互質的數的總和為phi[1]+phi[2]+.......phi[b/k].

2.對于區間[1,d/k]中大于b/k的數，每個數i在區間[1,b/k]中與其互質的數的個數，可以通過求其在在區間[1,b/k]中與其不互質的數的個數，再做減法。這一步就用容斥定理來做。找出[1,b/k]中可以被i的每個質因子整除的數的個數求和，減去可以被其任意兩個質因子整除的數的個數，加上可以被其任意三個質因子整除的數的個數。。。。。。

代碼：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define M 100005

int phi[M],prime[100];
int a,b,c,d,k;

void euler_phi()
{
    int i,j;
    //memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(i=2;i<=100000;i++)
    if(!phi[i])
    {
        for(j=i;j<=100000;j+=i)
        {
            if(!phi[j])
                phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}

ll slove(int n)   //求區間1~b中有多少數與n不互質
{
    //memset(prime,0,sizeof(prime));
    int i,num=0;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            prime[num++]=i;
            while(n%i==0)
                n=n/i;
        }
    }
    if(n!=1)
        prime[num++]=n;

    ll sum=0;
    for(ll msk=1;msk<(1ll<<num);msk++)
    {
        ll mult=1,bits=0;
        for(ll i=0;i<num;i++)
        {
            if(msk&(1ll<<i))
            {
                bits++;
                mult*=prime[i];
            }
        }
        if(bits&1)
            sum+=((ll)b)/mult;
        else
            sum-=((ll)b)/mult;
    }
    return sum;
}

int main()
{
    euler_phi();
    int i,T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0)
        {
            printf("Case %d: 0\n",++cas);
            continue;
        }
        if(b>d)
        {
            int temp=b;
            b=d;
            d=temp;
        }
        ll ans=0;
        b=b/k;
        d=d/k;
        for(i=1;i<=b;i++)
        {
            ans+=phi[i];
        }
        for(i=b+1;i<=d;i++)
        {
            ans+=(ll)b-slove(i);
        }
        printf("Case %d: %lld\n",++cas,ans);
    }
    return 0;
}