POJ 3904 Sky Code (互素的四元组+容斥原理)

￡神魔★判官ぃ 2022-07-26 08:39 30阅读 0赞

POJ 3904 Sky Code (互素的四元组+容斥原理) ：[http://poj.org/problem?id=3904][http_poj.org_problem_id_3904]

题目大意：

给定n个数据，求其中互素的四元组（两两可以不互素）的个数。

题目分析：

要想求互素的四元组的个数，我们可以先去求不互素的四元组的个数ans，然后所有可能的取法数C(n,4)（n个里面取4个的组合数公式）减去不互素的四元组的个数。

考虑到不互素的四元组必满足四个数必有除了1以外的大于等于一个的因子（可能是素数，也可能不是素数），则可以对每一个数都进行因子分解，由于这些因子可能会被重复的计算，所以应用容斥原理，对于每一个因子，该因子若含有除了1以外的奇数个因子的话，则加上，否则，含有偶数个因子的话，则减去；举例说明：n个数中，以2为因子的数有a个，以3为因子的数有b个，以6为因子的数有c个，则满足不互素的四元组的个数有C(a,4)+C(b,4)-C(c,4)个。

关于代码实现中的二进制枚举部分，有几个关键的地方：（转）

（1）： 理解cnt\[i\]表示含有因子i的数据的个数（2,4,6,8,10这组数据中cnt\[i\]=5） num\[i\]表示因子i含有的不同素因子的个数（num\[6\]=2,减）

（2）： 怎样得到cnt\[i\]、num\[i\]，或者说怎样实现素因子组合？用到了二进制表示的思想，第j位的1表示第j个素因子参与累乘，0表示不参与累乘，比如含有素因子2\*3\*5\*7，1010表示2\*1\*5\*1，0001表示1\*1\*1\*7，以此类推……这样，只要素因子分解完记录含有素因子的个数tol，那么就有tol位二进制，注意到2\*3\*5\*7\*11\*13>10000，所以最多有6位二进制；对于任意一个范围内的数i，遍历所有位j（从低位到高位），i&(1<<j)==1，表示i的第j位二进制为1，意思是第j个素因子参与累乘；依据这样的意义，遍历二进制范围内的所有数i和i对应的所有二进制数位j，更新数组cnt\[k\]和num\[k\]即可！

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int MAXN=10005;
    
    long long  prime[MAXN];  //存放素因子
    long long C[MAXN];
    long long count[MAXN];
    long long num[MAXN];
    
    void zuheshu() //计算组合数，i个里面选4个
    {
        memset(C,0,sizeof(C));
        for(long long i=4; i<=10000; i++)
        {
            C[i]=i*(i-1)*(i-2)*(i-3)/24;
        }
    }
    
    void divide(int x)
    {
        long long tol=0;
        for(long long i=2;i*i<=x;i++)
        {
            if(x%i==0)
            {
                prime[tol++]=i;
            }
            while(x%i==0)
            {
                x/=i;
            }
        }
        if(x!=1)
        {
            prime[tol++]=x;
        } 
        //对x进行素因子分解，tol表示素因子的个数
        for(long long i=1;i<(1<<tol);i++) //利用二进制的每一位0,1对素因子进行组合
        {
            long long k=1;
            long long sum=0;
            for(long long j=0;j<tol;j++) //从低位到高位遍历，找i在哪一位是1
            {
                if(i&(1<<j)) //与运算，j位为1，执行if语句
                {
                    k*=prime[j];//累乘素因子
                    sum++;
                }
            }
            count[k]++; //记录当前因子的个数
            num[k]=sum; //记录当前因子是由多少个素因子组成
        }
    }
    
    int main()
    {
        long long  n,m;
        zuheshu();
        while(scanf("%lld",&n)!=EOF)
        {
            memset(count,0,sizeof(count));
            memset(num,0,sizeof(num));
            for(int i=0; i<n; i++)
            {
                scanf("%lld",&m);
                divide(m); //素因子分解，并统计
            }
            long long ans=0;
            for(long long i=0;i<=10000;i++)
            {
                if(count[i])
                {
                    if(num[i]%2)
                    {
                        ans+=C[count[i]];
                    }
                    else
                    ans-=C[count[i]];
                }
            }
            printf("%lld\n",C[n]-ans);
        }
        return 0;
    }

[http_poj.org_problem_id_3904]: http://http://poj.org/problem?id=3904