poj3904 Sky Code（容斥原理）

• 给出n个数，问有多少组(a,b,c,d)公约数为1，注意并不一定两两互质！因为不一定两两都互质，那么从相反的方向着手比较方便！即先统计出(a,b,c,d)公约数>1的对数，然后用总数减去即可！

• 容斥原理，以2为因子的数有a个，3为因子 的数有b个，6为因子的数有c个，n个数不互质的四元组个数为C(4,a)+C(4,b)-C(4,c) （含奇数个素因子的加，偶数个素因子的减），下面就是统计出2,3,5这些因子的倍数的个数，对C(4,a)容斥！
• 即对n素因数分解为cnt个素数，再对cnt进行按位枚举，负责度（2^(logn)）= O(n)
• 注意这和求一个数的所有因数有所不同，因为是1~n，所以每个素数只会出现一次，更容易求得

//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B){
    (A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B){
    (A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e4+10; 

 
ll C4[maxn],num[maxn],vist[maxn],prime[maxn];
void Init()
{
	for(ll i=4;i<maxn;i++)
		C4[i]=i*(i-1)*(i-2)*(i-3)/24;
}
 
void make_count(int m)
{
	int tmp,flag,cnt=0;
	for(int i=2;i*i<=m;i++)
		if(m&&m%i==0)
		{
			prime[cnt++]=i;
			while(m&&m%i==0)
				m/=i;
		}	
	if(m>1) prime[cnt++]=m;
	for(int i=1;i<(1<<cnt);i++)
	{
		tmp=1,flag=0;
		for(int j=0;j<cnt;j++)
			if(i&(1<<j))
				flag++,tmp*=prime[j];
		num[tmp]++;  //当前因子出现的次数
		vist[tmp]=flag; //记录当前因子是由多少个素因子组成
	}
}
 
int main()
{
	Init();
	int n,x;
	while(~scanf("%d",&n))
	{
		memset(num,0,sizeof(num));
		memset(vist,0,sizeof(vist));
		rep(i,0,n-1)
		{
			scanf("%d",&x);
			make_count(x);
		}
		ll ans=0;
		rep(i,1,maxn-1)
			if(num[i])
			{
				if(vist[i]&1)
					ans+=C4[num[i]];
				else
					ans-=C4[num[i]];
			}
		printf("%I64d\n",C4[n]-ans);			
	}
	return 0;
}