HDU1695(歐拉+容斥)

GCD

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5646    Accepted Submission(s): 2045

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

Source 2008 “Sunline Cup” National Invitational Contest

題意：給定兩個區間 [a,b],[c,d]，在兩個區間中分别區一個數，使得GCD(x,y)=k;

分析：很自然的我們可以想到GCD(x/k,y/k)=1;是以相當于在區間[1/k,b/k],[1/k,d/k]中取兩區間中的元素x,y使得GCD(x,y)=1；

由于GCD(x,y)與GCD(y,x)是一樣的，我們假設x<y,于是可以先取小區間中的。

由于GCD(X,Y)=1；是以小區間可以計算為

ans+=phi(1)+phi(2)+.....+phi(b/k);(假設b/k<d/k);

對于區間[b/k+1,d/k]，設y為區間的一個元素，我們可以對y進行素因子分解，于是得到集合{p1,p2,p3,......},可以通過求gcd(x,y)!=1來求gcd(x,y)=1;中間需要用到容斥原來來進行統計能被這些素數整除的數的個數。

我們用b/k減去與i不互質的數的個數得到,求與i不互質的數的個數時就用到容斥原理,設i的素因子分别的p1,p2...pk,則1..b/k中p1的倍數組成集合A1,p2的倍數組成集合A2,p3到A3.....pk到Ak,　由于集合中會出現重複的元素,　是以用容斥原理來求A1并A2并A3.....并Ak的元素的數的個數.

A1并A2并A3并A4并..并.AK=一個因子的倍數的個數-兩個因子的倍數的個數+三個因子的倍數的個數。。。。。。(奇加偶減)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;

const int maxn = 100001;

int num[maxn],p[maxn][20];//每個數的素因子個數，每個數的素因子
LL eular[maxn];//每個數的歐拉函數值之和

void init(){//篩發得到數的素因子
    eular[1]=1;
    for(int i=2;i<maxn;i++){
        if(!eular[i]){
            for(int j=i;j<maxn;j+=i){
                if(!eular[j])
                    eular[j]=j;
                eular[j]=eular[j]*(i-1)/i;
                p[j][num[j]++]=i;
            }
        }
        eular[i]+=eular[i-1];
    }
}

LL dfs(int id,int b,int now){//求不大于b的數中,與now不互質的數的個數;
    LL ans=0;
    for(int i=id;i<num[now];i++)//容斥原理來求A1并A2并A3.....并Ak的元素的數的個數.
        ans+=b/p[now][i]-dfs(i+1,b/p[now][i],now);
    return ans;
}

int main(){
    int t,a,b,c,d,k,ca=1;
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("Case %d: ",ca++);
        if(k==0){
            puts("0");
            continue;
        }
        if(b>d)
            swap(b,d);
        b/=k,d/=k;
        LL ans=eular[b];
        for(int i=b+1;i<=d;i++)
            ans+=b-dfs(0,b,i);
        printf("%I64d\n",ans);
    }
    return 0;
}