题目大意：给定n个不大于1w的数字，求出其中四个数字a，b，c，d使得gcd(a,b,c,d)==1的组数；
解析：起初我就想正面硬杠，奈何重复太多，实在力不从心~~~
从网上大神那里得知，此题应用的是容斥原理，大概意思是我们正面不行就玩阴的，啊不，从反面来处理，求出gcd(a,b,c,d)>1的组数，最后做差就行了。
做法：将每个数字进行质因数分解，然后求出它的所有因子，并求出该因子含有的质因子个数，然后进行奇加偶减。
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define N 10005 #define ll long long using namespace std; int n,f[N],sum[N]; ll x,ans,c[N]; void at_first() { memset(c,0,sizeof(c)); for(ll i=4;i<N;i++) c[i]=i*(i-1)*(i-2)*(i-3)/24; } void slove(int x) { int prim[N],tot=0; for(int i=2;i*i<=x;i++) { if(x%i==0) prim[tot++]=i; while(x%i==0)x/=i; } if(x>1)prim[tot++]=x; for(int i=1;i<(1<<tot);i++) { long long k=1,su=0; for(int j=0;j<tot;j++) { if(i&(1<<j)) { k*=prim[j];su++; } } f[k]++; sum[k]=su; } } int main() { at_first(); while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { scanf("%d",&x); slove(x); } ans=0; for(int i=2;i<N;i++) { if(f[i]) { if(sum[i]%2) ans+=c[f[i]]; else ans-=c[f[i]]; } } printf("%lld\n",c[n]-ans); } return 0; }
