HDU 1695-GCD（容斥原理+欧拉函数）

男娘i 2022-09-25 02:26 74阅读 0赞

# GCD #

**Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 9601 Accepted Submission(s): 3582**

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][2008 _Sunline Cup_ National Invitational Contest]

Recommend

wangye | We have carefully selected several similar problems for you: [1689][] [1690][] [1693][] [1691][] [1698][]

## 题目意思： ##

给出5个数，a,b,c,d,k，在\[a,b\]闭区间内找一个数x，再在 \[c,d\]中找一个数y，使得(x,y)的最大公约数是k。

请找出满足条件的不同的 (x,y)的对数，其中x与y交换位置视为同一种。

## 解题思路： ##

gcd(x,y)=k，则 gcd(x/k,y/k)=1。

变换区间，1~b中k的最大倍数为int(b/k)\*k，新区间为1~int(b/k)，相应另一个新区间为 1~int(d/k)。

令 b'=int(b/k)，d'=int(d/k)，且b'<=d'，则新区间为：\[1,b'\]和\[b'+1,d'\]。

前一个区间：\[1,b\]；后一个区间：任取一个数i，求\[1,b\]内所有能被i的质因数整除的数的个数，然后用b'减去。

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 100010
    typedef long long ll;
    int a[maxn];
    struct Number
    {
        int cnt;//每个数质因数的个数
        int prime[20];//每个数的质因数数组
    } n[maxn];
    ll e[maxn];//欧拉函数打表用
    void oula()//欧拉函数
    {
        e[1]=1;
        memset(n,0,sizeof(Number)*maxn);//初始化清零
        for(int i=2; i<=maxn; ++i)
        {
            if(!e[i])
                for(int j=i; j<=maxn; j+=i)
                {
                    if(!e[j]) e[j]=j;
                    e[j]=e[j]*(i-1)/i;//欧拉函数打表
                    n[j].prime[n[j].cnt++]=i;//保存质因数
                }
            e[i]+=e[i-1];
        }
    }
    
    ll inc(int index,int b,int m)//容斥原理，递归
    {
        ll r=0,t;
        for(int i=index; i<n[m].cnt; ++i)
        {
            t=b/n[m].prime[i];
            r+=t-inc(i+1,t,m);
        }
        return r;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        oula();//预处理
        int t,ca=0;
        cin>>t;
        while(t--)
        {
            int a,b,c,d,k;
            cin>>a>>b>>c>>d>>k;
            if(k==0)//注意特判
            {
                cout<<"Case "<<++ca<<": 0"<<endl;
                continue;
            }
            if(b>d) swap(b,d);//使得b始终大于d
            b/=k;
            d/=k;
            ll ans=e[b];//前一个区间：[1,b]
            for(int i=b+1; i<=d; ++i)//后一个区间：任取一个数i，求[1,b]内所有能被i的质因数整除的数的个数
                ans+=b-inc(0,b,i);
            cout<<"Case "<<++ca<<": "<<ans<<endl;
        }
        return 0;
    }
    
    /**
    2
    1 3 1 5 1
    1 11014 1 14409 9
    **/

[2008 _Sunline Cup_ National Invitational Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=2008+%A1%B0Sunline+Cup%A1%B1+National+Invitational+Contest&source=1&searchmode=source
[1689]: http://acm.hdu.edu.cn/showproblem.php?pid=1689
[1690]: http://acm.hdu.edu.cn/showproblem.php?pid=1690
[1693]: http://acm.hdu.edu.cn/showproblem.php?pid=1693
[1691]: http://acm.hdu.edu.cn/showproblem.php?pid=1691
[1698]: http://acm.hdu.edu.cn/showproblem.php?pid=1698