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);
    }
}