Triple ACM HDU 3908(数学の問題、何種類の組み合わせを探します)

Triple
Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others)Total Submission(s): 387    Accepted Submission(s): 153
Problem Description
Given many different integers, find out the number of triples (a, b, c) which satisfy a, b, c are co-primed each other or are not co-primed each other. In a triple, (a, b, c) and (b, a, c) are considered as same triple.
 
Input
The first line contains a single integer T (T <= 15), indicating the number of test cases.
In each case, the first line contains one integer n (3 <= n <= 800), second line contains n different integers d (2 <= d < 10
5) separated with space.
 
Output
For each test case, output an integer in one line, indicating the number of triples.
 
Sample Input
1 6 2 3 5 7 11 13
 
Sample Output
20
 
Source
2011 Multi-University Training Contest 7 - Host by ECNU
 
Recommend
xubiao
 
 

/*
    ：
  n  ，     1    2 a，b，c      。
  1：      
  2：       
    ：
    a[i]:  i         。
 b[i]：  i          。
  a[i] * b[i]   i            。
    ，   i       ，              abc，       。
  ，    C(n,3)- sum/2  。

*/
#include<stdio.h>
#define MAXN 10010
int a[MAXN],b[MAXN],num[MAXN];
int gcd(int da,int xiao)//            
{
    int temp;
    while(xiao!=0)
    {
        temp=da%xiao;
        da=xiao;
        xiao=temp;
    }    
    return da;
} 
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    int T,n,i,j;
    int sum;//       
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            a[i]=0;//a[i]   num[i]        
            b[i]=0;//a[i]   num[i]        
        }
        sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {
                if(gcd(num[i],num[j])==1)  a[i]++;
                else  b[i]++;
            } 
            for(j=i+1;j<=n;j++)
            {
                if(gcd(num[i],num[j])==1)  a[i]++;
                else  b[i]++;
            }
            sum+=a[i]*b[i];       
        }
        int cnt=n*(n-1)*(n-2)/6-sum/2;
        printf("%d
",cnt);       
    } 
    return 0;   
}