POJ 3904 Sky Code

题目地址： http://poj.org/problem?id=3904

题意：给出n个数，问找出4个数满足4个数最大公约数为1，最多有多少组。
思路：容斥原理，遍历每个数的素因子，奇数个加偶数个减，然后C(n,4)-sum。

//求得是n个数中，有多少组(a,b,c,d)的公约数为1，值得注意的是这四个数不一定两两互质。  
//所以我们从它的反面考虑，先求出公约数不为1的个数。  
//思路：把每个数素数分解，记录不重复素因子所能组成的因子，把这些因子的总数统计，并且统计每个因子是由多少个素因子组成  
//如这n个数中含2的个数为a,含3的个数为b,含6的个数为c,那么公约数大于1的总数为p=c(a,4)+c(b,4)-c(c,4),总的个数为c(n,4)  
//用c(n,4)-p即为所求

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cfloat>
using namespace std;

typedef __int64 LL;
const int N=10005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL n,m,pri[N],num[N],co[N],p[N];

void init()
{
    memset(p,0,sizeof(p));
    memset(num,0,sizeof(num));
    for(LL i=4;i<N;i++)//p[i]表示总共有多少种方法
        p[i]=i*(i-1)*(i-2)*(i-3)/24;
}

LL prime(LL x)
{
    LL i,j,numi=0;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        {
            pri[numi++]=i;
            while(x%i==0)
                x/=i;
        }
    if(x>1)
        pri[numi++]=x;
    return numi;
}

void dfs(LL k)
{
    LL i,j,t,numi;
    numi=prime(k);
    LL sum=0;
    for(i=1;i<(1<<numi);i++)
    {
        LL temp=1,k=0;
        for(j=0;j<numi;j++)
            if(i&(1<<j))
            {   temp*=pri[j];   k++;    }
        co[temp]++;//记录当前因子的个数
        num[temp]=k;//记录当前因子是由多少个素因子组成
    }
}

int main()
{
    LL i,j,T;
    init();
    while(~scanf("%I64d",&n))
    {
        memset(co,0,sizeof(co));
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&m);
            dfs(m);
        }
        LL sum=0;
        for(i=0;i<N;i++)
        {
            if(!co[i])   continue;
            if(num[i]&1)    sum+=p[co[i]];
            else    sum-=p[co[i]];
        }
        printf("%I64d
",p[n]-sum);
    }
    return 0;
}