http://poj.org/problem?id=3904

Stancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem – Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four stars such that the only common divisor of their numbers is 1. Nasty, isn’t it? Fortunately, Stancu has succeeded to limit the number of the interesting stars to N but, any way, the possible subsets of four stars can be too many. Help him to find their number and to decide if there is a chance to break the system.

Input

In the input file several test cases are given. For each test case on the first line the number N of interesting stars is given (1 ≤ N ≤ 10000). The second line of the test case contains the list of ID numbers of the interesting stars, separated by spaces. Each ID is a positive integer which is no greater than 10000. The input data terminate with the end of file.

Output

For each test case the program should print one line with the number of subsets with the asked property.

 

题意：在n个数中，任选4个，这4个数gcd为1的方案数有多少？

思路：gcd为1很难做，反过来做gcd不是1的方案数，答案就是C(n,4)-gcd不是1的方案数

要对每一个数分解为若干质因子之积，记录以所有素数及素数组合为因子的数的个数，比如，是2的倍数的数有x个，是3的倍数的数有y个，是6的倍数的数有z个，那么含2或3作为因子的数的个数是C(x,4)+C(y,4)-C(z,4)，这样对k个素数的2^k中组合进行容斥。

不同于hdu4135那一道容斥的是，那一道是把小于1e9的数分解为k个不同素数，素数乘积比阶乘增长更快，1e9分解下来也没有多少素数

而这道题，有n个不同的数，每个数虽然只是小于1w，但是n个数的因子种类总数为小于1w的素数总数1229个，遍历2^1229种组合是不可能的，因此对于每一个数分解为k个不同素数，遍历2^k种组合，最后就很简单了。

注意种类数要开long long，因为C（n，4）差不多4次方，很大。

做这题有几点收获：

二进制枚举比队列数组快很多，多组数据每组1w个数字scanf比cin快很多，数组比vector快一点，vector.size()和一个变量速度没区别。

二进制+cin900+ms，队列数组+scanf900+ms，二进制+scanf100+ms

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long

int n,x,num[10005];

void solve(int n)
{
	vector<int> prime;
	int m=sqrt(n+0.5);
	for(int i=2;i<=m;i++)if(n%i==0)
	{
		prime.push_back(i);
		while(n%i==0)n/=i;
	}
	if(n>1)prime.push_back(n);
	for(int i=1;i<(1<<prime.size());i++)
	{
		int k=1,cnt=0;
		for(int j=0;j<prime.size();j++)if(i&(1<<j))
		{
			cnt++;
			k*=prime[j];
		}
		if(cnt&1)num[k]++;
		else num[k]--;
	}
}

ll C(ll n){return n*(n-1)*(n-2)*(n-3)/24;}

ll calc()
{
	ll ans=0;
	for(int i=1;i<=10000;i++)
	{
		if(num[i]>0)ans+=C(num[i]);
		else ans-=C(-1*num[i]);		
	}
	return C(n)-ans;
}

int main()
{
//	freopen("input.in","r",stdin);
//	freopen("output.out","w",stdout);
	while(cin>>n)
	{
		memset(num,0,sizeof(num));
		for(int i=1;i<=n;i++)
		{
			cin>>x;
			solve(x);
		}
		cout<<calc()<<endl;
	}	
	return 0;
}