首页 > 代码库 > POJ 3904 Sky Code 容斥原理

POJ 3904 Sky Code 容斥原理

求一串序列里面的4个数互质 的个数

依然是反向考虑,求序列里面四个数不互质的个数,最后用总数减去即可

求四个数不互质的个数,直接求不好求,不如求公因子为2的,为3的,为。。。的有多少个,

然后用容斥原理,先求出为2的,为3的。。再减去为2和3的,为3和5的。。。再加上公因子为3个的。。。

即可

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing namespace std;const int N = 10010;LL num[N];void init(){    for (int i=4;i<N;i++){        num[i]=(LL)i*(i-1)*(i-2)*(i-3)/24;    }}int n;int vis[N],t[N],prime[N],ret;void proc(int x){    ret=0;    for (int i=2;i*i<=x;i++){        if (x%i==0){            prime[ret++]=i;            while (x%i==0) x/=i;        }    }    if (x>1) prime[ret++]=x;    for (int i=1;i<(1<<ret);i++){        int flag=0,tmp=1;        for (int j=0;j<ret;j++){            if ((1<<j)&i){                tmp*=prime[j];                flag++;            }        }        vis[tmp]++;        t[tmp]=flag;    }}int main(){    int a;    init();    while (scanf("%d",&n)!=EOF)    {        memset(vis,0,sizeof vis);        memset(t,0,sizeof t);        for (int i=0;i<n;i++){          scanf("%d",&a);          proc(a);        }        LL ans=0;        for (int i=1;i<N;i++){            if (vis[i]>0){                if (t[i]&1) ans+=num[vis[i]];                else ans-=num[vis[i]];            }        }        printf("%lld\n",num[n]-ans);    }    return 0;}

 

POJ 3904 Sky Code 容斥原理