Description
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.
(n<=10000 ai<=10000)
完美的逆向思维，枚举每一个gcd为一个数的个数，然后排列组合，算出不行的个数，显然会有包含的繁琐关系，所以进行容斥。
我是先把每个数的约数计算出来，然后每个约数的出现次数记录（4的话只加一次2）；再进行容斥。
另外还有一种方法，就是把<=10000的数的约数统计一下，并记录每个数含有不同质因子的个数，奇数就加，偶数就减。代码好写。
另外就是有很多细节啊什么的，（坑人的sqrt()）;
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#define LL long long
using namespace std;
int n,a[10100];
LL ans;
int prime[10100],cnt,num[10100],c[10100],tot;
bool v[10100];
void quick_prime()
{
for(int i=2;i<10000;i++)
{
if(!v[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<10000;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void cut(int x)//质因数分解再dfs会TLE，直接根号n分解约数，虽然有些约数无用，像4=2*2；
{
int lim=(int)(sqrt(1.0*x));//sqrt()里一定是double！！！沃日！！
for(int i=1;i<=lim;i++)
{
if(x%i==0)
{
num[i]++;
if(x/i!=i) num[x/i]++;
}
}
}
LL C(int x)
{
LL re=1;
for(int i=0;i<4;i++)
re*=(x-i);
re>>=3;
re/=3;
return re;
}
void dfs(int cur,int now,bool flag)
{
if(cur>cnt) return ;
if(now>10000) return ;
int p=now*prime[cur];
if(p<=10000&&num[p]>3)///RE上百次，只因顺序写错
{
if(flag) ans+=C(num[p]);
else
ans-=C(num[p]);
dfs(cur+1,now,flag);
dfs(cur+1,p,!flag);
}
else
dfs(cur+1,now,flag);//想一想为什么不继续dfs p 了
}
int main()
{
quick_prime();
while(scanf("%d",&n)!=EOF)
{
memset(num,0,sizeof(num));
for(int x,i=1;i<=n;i++)
{
scanf("%d",&x);
cut(x);
}
/*for(int i=1;i<=10;i++)
printf("%d ",num[i]);*/
if(n<4)//不特判也行，因为C（x,4）当x<=4时==0
{
printf("0\n");
continue;
}
ans=C(n);
dfs(1,1,0);
printf("%lld\n",ans);
}
return 0;
}