hdu 5072 Coprime 2014 Asia AnShan Regional Contest 单色三角模型+容斥 好题

hdu 5072 Coprime 2014 Asia AnShan Regional Contest 单色三角形模型+容斥 好题！

题意：给了n个不同的数，要求有多少个三元组，两两互质 或者 两两不互质。

思路：

        单色三角形模型：给定空间的n个点，其中没有三点共线。每两个点之间都用红色或者黑色线段连接，求3条边同色的三角形个数。

       我们从反面考虑，只要求出了非单色三角形，就能间接得到单色三角形的个数。在每个非单色三角形中，恰好有两个顶点连接两

个不同颜色的边，而且对于一个点有两个不同颜色的边那么必然对应一个非单色三角形，如果第i个点连接了a[i]条红边，n-1-a[i]条黑

边，那么这些边属于a[i](n-1-a[i])个非单色三角形。每个非单色三角形考虑了2次(因为一个非单色三角形有2个连接异色边的点)，因此

最终答案应该除2，所以ans=1/2sigma{a[i]×(n-1-a[i])}。那么最终答案为n×(n-1)×(n-2)/6-ans。

       那么接下来就是处理互质的个数。只需要分解质因数，预处理，然后容斥。详见代码：

/*********************************************************
  file name: hdu5072.cpp
  author : kereo
  create time:  2015年01月30日 星期五 22时37分46秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,cnt,fcnt;
int a[MAXN],prime[MAXN],num[MAXN],factor[N][2];
void getprime(){
    cnt=0;
    memset(prime,0,sizeof(prime));
    for(int i=2;i<MAXN;i++){
        if(!prime[i]) 
            prime[++cnt]=i;
        for(int j=1;j<=cnt && prime[j]<=MAXN/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j] == 0)
                break;
        }
    }
}
int getfactor(int x){
    fcnt=0;
    for(int i=1;prime[i]<=x/prime[i];i++){
        if(x%prime[i] == 0){
            factor[fcnt][0]=prime[i];
            factor[fcnt][1]=0;
            while(x%prime[i] == 0){
                factor[fcnt][1]++;
                x/=prime[i];
            }
            fcnt++;
        }
    }
    if(x!=1){
        factor[fcnt][0]=x; factor[fcnt++][1]=1;
    }
    return fcnt;
}
int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(num,0,sizeof(num));
        getprime();
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
           // printf("-------a[i]=%d----------\n",a[i]);
            getfactor(a[i]);
            for(int st=1;st<(1<<fcnt);st++){
                int res=1;
                for(int k=0;k<fcnt;k++)
                    if(st&(1<<k))
                        res*=factor[k][0];
                num[res]++;
               // printf(" %d",res);
            }
            //printf("\n");
        }
        /*for(int i=0;i<=10;i++)
            printf("%d ",num[i]);
        printf("\n");*/
        ll ans=0;
        for(int i=0;i<n;i++){
            getfactor(a[i]);
            //printf("--------------a[i]=%d----------\n",a[i]);
            ll cnt1=0;
            for(int st=1;st<(1<<fcnt);st++){
                int res=1,cnt2=0;
                for(int k=0;k<fcnt;k++)
                    if(st & (1<<k))
                        cnt2++,res*=factor[k][0];
               // printf("res=%d cnt2=%d num[res]=%d\n",res,cnt2,num[res]);
                if(cnt2&1)
                    cnt1+=num[res];
                else
                    cnt1-=num[res];
            }
            if(a[i] ==1) //特殊处理下1
                cnt1++;
           // printf("a[i]=%d cnt1=%lld\n",a[i],cnt1);
            ans+=(cnt1-1)*(n-cnt1);
        }
        //printf("ans=%lld\n",ans);
        ans=(ll)n*(ll)(n-1)*(ll)(n-2)/6-ans/2;
        printf("%I64d\n",ans);
    }
	return 0;
}