HDU5072 给了n个不同的数，要求有多少个三元组，两两互质或者两两不互质。模型请参考《算法竞赛入门经典训练指南》 p105 问题6 （训练指南真的是神书啊，多次区域赛都有类似题了，卧槽）现场的时候明显想复杂了，用了复杂方法搞。其实从方面考虑。直接对每个数，求有多少个和它互质的，多少个和它不互质的，相乘累加。。就是反面的2倍了。至于如何求有多少个互质的，直接质因数分解，然后容斥就可以了。 HDU 时限有点紧，现场可以随便搞！

Coprime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 556 Accepted Submission(s): 254

Problem Description

There are n people standing in a line. Each of them has a unique id number. Now the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y. We want to know how many 3-people-groups can be chosen from the n people.

Input

The first line contains an integer T (T ≤ 5), denoting the number of the test cases. For each test case, the first line contains an integer n(3 ≤ n ≤ 105), denoting the number of people. The next line contains n distinct integers a1, a2, . . . , an(1 ≤ ai ≤ 105) separated by a single space, where ai stands for the id number of the i-th person.

Output

For each test case, output the answer in a line.

Sample Input

1 5 1 3 9 10 2

Sample Output

Source

2014 Asia AnShan Regional Contest

/* ***
Author :kuangbin
Created Time :2014/10/30 12:20:43
File Name :E:\2014ACM\2014现场赛\鞍山\C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100000;
int prime[MAXN+1];
void getPrime(){
memset(prime,0,sizeof(prime));
for(int i = 2;i <= MAXN;i++){
if(!prime[i])prime[++prime[0]] = i;
for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++){
prime[prime[j]*i] = 1;
if(i%prime[j] == 0)break;
}
}
}
int factor[100][2];
int fatCnt;
inline int getFactor(int x){
fatCnt = 0;
for(int i = 1;prime[i] <= x/prime[i];i++)
if(x%prime[i] == 0){
factor[fatCnt][0] = prime[i];
factor[fatCnt][1] = 0;
while(x%prime[i] == 0){
factor[fatCnt][1]++;
x /= prime[i];
}
fatCnt++;
}
if(x != 1){
factor[fatCnt][0] = x;
factor[fatCnt++][1] = 1;
}
return fatCnt;
}
int a[100010];
int num[100010];
int two[20];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n;
scanf(“%d”,&T);
two[0] = 1;
for(int i = 1;i < 20;i++)
two[i] = two[i-1]<<1;
getPrime();
while(T–){
scanf(“%d”,&n);
memset(num,0,sizeof(num));
for(int i = 0;i < n;i++){
scanf(“%d”,&a[i]);
getFactor(a[i]);
for(int j = 0;j < two[fatCnt];j++){
int tmp = 1;
for(int k = 0;k < fatCnt;k++)
if(j&two[k]){
tmp = factor[k][0];
}
num[tmp]++;
}
}
long long ret = 0;
for(int i = 0;i < n;i++){
getFactor(a[i]);
int cc = 0;
for(int j = 0;j < two[fatCnt];j++){
int tmp = 1;
int cnt = 0;
for(int k = 0;k < fatCnt;k++)
if(j&two[k]){
cnt++;
tmp = factor[k][0];
}
if(cnt&1)cc -= num[tmp];
else cc += num[tmp];
}
if(a[i] == 1)cc–;
ret += (long long)cc(n-1-cc);
}
long long tot = (long long)n(n-1)*(n-2)/6;
printf(“%I64d\n”,tot-ret/2);
}
return 0;
}