poj3904 Sky Code------容斥复习
//这题很久以前做过了，好久没有接触过容斥了，拿来复习复习//求得是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即为所求#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;#define maxn 10005long long count[maxn];long long num[maxn];long long p[maxn];long long prime[maxn];void init(){ memset(p,0,sizeof(p)); memset(num,0,sizeof(num)); for(long long i=4;i<maxn;i++) p[i]=i*(i-1)*(i-2)*(i-3)/24;}void solve(long long n){ long long tol=0; for(long long i=2;i*i<=n;i++) { if(n%i==0) { prime[tol++]=i; } while(n%i==0) n/=i; } if(n!=1) prime[tol++]=n; for(long long i=1;i<(1<<tol);i++) { long long k=1; long long sum=0; for(long long j=0;j<tol;j++) { if(i&(1<<j)) { k*=prime[j]; sum++; } } count[k]++;//记录当前因子的个数 num[k]=sum;//记录当前因子是由多少个素因子组成 }}int main(){ init(); long long n; long long m; while(scanf("%lld",&n)!=EOF) { memset(count,0,sizeof(count)); for(long long i=0;i<n;i++) { scanf("%lld",&m); solve(m); } long long ans=0; for(long long i=0;i<maxn;i++) { if(count[i]) { if(num[i]%2) { ans+=p[count[i]]; } else ans-=p[count[i]]; } } cout<<p[n]-ans<<endl; }}
