hdu 1695 GCD (欧拉函数+容斥原理+素因子分解)

绝地灬酷狼 2022-07-25 15:58 176阅读 0赞

hdu 1695 GCD (欧拉函数+容斥原理+素因子分解) ：[http://acm.hdu.edu.cn/showproblem.php?pid=1695][http_acm.hdu.edu.cn_showproblem.php_pid_1695]

题面描述：

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

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

题目大意：

在x区间\[a,b\]和y区间\[c,d\]中出满足gcd(x,y)=k的(x,y)的对数。

题目分析：

数据不是暴力就能过的，需要用到莫比乌斯反演的思想，具体分析如下：

（1）由于gcd(x,y)=k满足gcd(x/k,y/k)=1，所以区间可以缩小为：\[1/k.b/k\]，\[1/k,d/k\]，问题也转化成为取两区间中的元素x,y，使得gcd(x,y)=1;

（2）由于gcd(y,x)=1和gcd(x,y)=1是相同的，假设x<y，于是可以先取小区间进行讨论，由于gcd(x,y)=1，利用欧拉函数，所以小区间可以计算为：

ans+=phi\[1\]+phi\[2\]+...+phi\[b\](用欧拉函数的递推形式保存起来即可);

（3）对于\[b/k+1,d/k\]，设y为区间的一个元素，则可以对y进行素因子分解，于是得到集合：\[p1,p2,p3,...\]，其中pi为素数，虽然是要求gcd(x,y)=1的组合，但反过来也可以求gcd(x,y)!=1的组合，于是可以用容斥原理进行统计能被这些素数整除的数的个数，最后相减求补数即可加到ans.

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    
    #define Maxn 100001
    
    using namespace std;
    
    int noprime[10000],no;
    int t,a,b,c,d,k,sum,casenum;
    
    void dfs(int i,int nu,int x,int mu) //容斥原理一般和递归一起用
    {
        if(nu==x)
        {
            sum+=b/mu;
            return;
        }
        if(i==no) return;
        dfs(i+1,nu+1,x,mu*noprime[i]);
        dfs(i+1,nu,x,mu);
        return;
    }
    
    int rong() //容斥定理
    {
        int s=0;
        for(int i=1; i<=no; i++)
        {
            sum=0;
            dfs(0,0,i,1);
            if(i&1)
                s+=sum;//奇数加，偶数减
            else s-=sum;
        }
        return b-s;//求的是互质的，取反
    }
    
    
    int main()
    {
        int phi[Maxn],prime[10000];//欧拉函数的递推形式
        bool boo[Maxn];
        for(int i=1; i<Maxn; i++) phi[i]=i;
        for(int i=2; i<Maxn; i+=2) phi[i]/=2;
        for(int i=3; i<Maxn; i+=2)
        {
            if(phi[i]==i)
            {
                for(int j=i; j<Maxn; j+=i)
                {
                    phi[j]=phi[j]/i*(i-1);
                }
            }
        }
    
        memset(boo,0,sizeof(boo));//线性筛素数
        boo[0]=boo[1]=1;
        int p=0;
        for(int i=2; i<Maxn; i++)
        {
            if(!boo[i])
                prime[p++]=i;
            for(int j=0; j<p&&i*prime[j]<Maxn; j++)
            {
                boo[i*prime[j]]=1;
                if(!(i%prime[j])) break;
            }
        }
    
        casenum=0;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
            if(k==0) //注意k等于0的情况
            {
                printf("Case %d: 0\n",++casenum);
                continue;
            }
            b/=k;
            d/=k;
            if(b>d)
            {
                int w=b;
                b=d;
                d=w;
            }
    
            long long ans=0;
            for(int i=1; i<=b; i++)
            {
                ans+=phi[i];
            }
            for(int i=b+1; i<=d; i++)
            {
                no=0;
                int aa=i;
                for(int j=0; j<p&&prime[j]*prime[j]<=aa; j++)
                    if(!(aa%prime[j]))
                    {
                        noprime[no++]=prime[j];
                        aa/=prime[j];
                        while(aa%prime[j]==0)
                        {
                            aa/=prime[j];
                        }
    //                        do
    //                        aa/=prime[j];
    //                        while(aa%prime[j]==0);
                    }
                if(aa>1)
                {
                    noprime[no++]=aa;
                }
                ans+=rong();
            }
            printf("Case %d: %lld\n",++casenum,ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1695]: http://http://acm.hdu.edu.cn/showproblem.php?pid=1695