Triple
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others) Total Submission(s): 1365 Accepted Submission(s): 549
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 < 105) 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
给你n个数，对于其中的任意n个数，a,b,c 要么两两互斥，要么a,b,c两两不互斥......
要你求出满足这一条件的组合数。
分析：
对于任意的三个数，a，b,c 我们知道有这些情况，0对互斥（即两两都不互斥），1对互斥，两对互斥，三对互斥（即两两互斥）。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=;
int item[maxn];
int gcd(int a,int b)
{
if(b==)return a;
return gcd(b,a%b);
}
int main()
{
int cas,n;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d",item+i);
int ans=;
for(int i=;i<n;i++)
{
int numa=,numb=;
for(int j=;j<n;j++)
{
if(i!=j)
{
if(gcd(item[i],item[j])==)numa++;
else numb++;
}
}
ans+=numa*numb;
}
printf("%d\n",(n*(n-)*(n-)/)-ans/);
}
return ;
}