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

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).

題意：輸入a1 a2 b1 b2 k；在a1~a2中選一個數a，b1~b2中選一個數b，使得gcd(a,b)=k，問一共有幾對(a,b)滿足條件(5，7) (7，5)屬于一種情況；

思路：将a1~a2，b1~b2之間的數都除以k分别得到最大值A，B那麼問題就轉化為求1~A之間與1~B之間互素的對數，即為1與（1~B）之間互素的個數+ 2與（1~B）互素的個數+……+A與（1~B）互素的個數，求法與a~b之間與n互素的個數

但是有一個問題就是重複的對數，舉個列子：1~3與1~5之間互素的個數

為（1，1）（1，2）（1，3）（1，4）（1，5）（2，1）（2，3）（2，5）（3，1）（3，2）（3，4）（3，5）每對的格式記為（aa，bb），我們發現重複的都是小于bb

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<cstdlib>
#include<ctime>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;
const int MAXN=+;
const int inf=;
vector<int>vec[MAXN];
ll x[MAXN];
void init(ll mm)//分解1~mm的素因子，并存到vector中
{
    for(ll i=; i<=mm; i++) vec[i].clear();
    for(ll j=; j<=mm; j++)
    {
        ll m=j;
        for(ll i=; i*i<=j; i++)
        {
            if(m%i==)
            {
                vec[j].push_back(i);
                while(m%i==)
                    m/=i;
            }
        }
        if(m>) vec[j].push_back(m);
    }
}
void judge(ll n)//求n的歐拉函數
{
    mem(x,);
    x[]=;
    for(ll i=;i<=n;i++)
    {
        if(!x[i])
        {
            for(ll j=i;j<=n;j+=i)
            {
                if(!x[j]) x[j]=j;
                x[j]=x[j]/i*(i-);
            }
        }
    }
}
ll Repulsion(ll n,ll m)//容斥原理，求1~n中與1~m互素的個數
{
    ll que[];
    ll sum=;
    for(ll i=; i<=m; i++)//求1~m中與n互素的個數
    {
        ll tot=vec[i].size();
        ll ans=,t=,k;
        que[t++]=-;
        for(ll j=; j<tot; j++)
        {
            k=t;
            for(ll v=; v<k; v++)
                que[t++]=que[v]*vec[i][j]*(-);
        }
        for(ll j=; j<t; j++)
            ans+=(n/que[j]);
        if(i<=min(n,m)) sum=sum+(n-ans)-x[i];
        else sum=sum+(n-ans);
    }
    return sum;
}
int main()
{
    int T,t=;
    judge();
    scanf("%d",&T);
    ll a1,b1,a2,b2,k;
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld",&a1,&b1,&a2,&b2,&k);
        if(k==) { printf("Case %d: 0\n",++t);continue; }
        ll n=,m=;
        for(ll i=a1;i<=b1;i++)
            n=max(n,i/k);
        for(ll i=a2;i<=b2;i++)
            m=max(m,i/k);
        if(n>m) swap(n,m);
        init(n);
        ll answer=Repulsion(m,n);
        printf("Case %d: %lld\n",++t,answer);
    }
}