学步园

 题意是求两两互质和两两不互质的三个数的个数

做法是：对第i个数分别求与它互质的和不互质的个数，x，y

sum(x,y)就是所有不符合条件的解得个数

ans=C(n,3)-sum/2

代码：

#include<stdio.h>
#include<string.h>

int d[805],A[805],B[805];

int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

int main()
{
    int i,j,t,n,ans,sum;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        scanf("%d",&n);
        ans=n*(n-1)*(n-2)/6;
        for(i=1;i<=n;i++)
            scanf("%d",&d[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i!=j)
                {
                    if(gcd(d[i],d[j])==1)
                        A[i]++;
                    else
                        B[i]++;
                }
            }
        for(i=1;i<=n;i++)
            sum=sum+A[i]*B[i];
        ans=ans-sum/2;
        printf("%d\n",ans);
    }
    return 0;
}