# 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

2011 Multi-University Training Contest 7 - Host by ECNU

对于任意的三个数，a，b,c 我们知道有这些情况，0对互斥（即两两都不互斥），1对互斥，两对互斥，三对互斥（即两两互斥）。

代码：

``` 1 #include<cstdio>
2 #include<cstring>
3 using namespace std;
4 const int maxn=100005;
5 int item[maxn];
6 int  gcd(int a,int b)
7 {
8     if(b==0)return a;
9     return gcd(b,a%b);
10 }
11 int main()
12 {
13   int cas,n;
14   scanf("%d",&cas);
15   while(cas--)
16   {
17     scanf("%d",&n);
18    for(int i=0;i<n;i++)
19     scanf("%d",item+i);
20    int ans=0;
21    for(int i=0;i<n;i++)
22    {
23          int numa=0,numb=0;
24         for(int j=0;j<n;j++)
25      {
26          if(i!=j)
27          {
28            if(gcd(item[i],item[j])==1)numa++;
29            else numb++;
30          }
31      }
32       ans+=numa*numb;
33    }
34     printf("%d\n",(n*(n-1)*(n-2)/6)-ans/2);
35   }
36  return 0;
37 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

### HDU 2147 kiki's game(规律，博弈)

kiki's game Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 40000/10000 ...

2856

### hdu 4405Aeroplane chess(概率DP)

Aeroplane chess Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

3255

### HDUOJ-----Climbing Worm

Climbing Worm Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2855

### HDU 4247 Pinball Game 3D(cdq 分治+树状数组+动态规划)

Pinball Game 3D Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/...

2814

### hdu-----（1151）Air Raid（最小覆盖路径）

Air Raid Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (...

3224

### poj----Maximum sum(poj 2479)

Maximum sum Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3...

2946

### Ignatius and the Princess IV hdu 1029

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32767 K (Java/Oth...

962

### HDU-1011 Starship Troopers（树形dp）

Starship Troopers Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536...

3497

### HDUOJ----1170Milk

Milk Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

28010

### HDU 3450 Counting Sequences（线段树）

Counting Sequences Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

3086