Prime
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 84 Solved: 12
[Submit][Status][Web Board]
Description
如果a,b的最大公约数是1，说明a,b是一对互素的数，给定你n个数字，希望你找出互素的数的对数
Input
第一行输入一个正整数T，表示数据组数
每组数据第一行输入一个正整数n，表示数字的个数(n<=10000)
接下来一行输入n个正整数，每个数字大小不超过1000。
Output
输出互素的数的对数
Sample Input
1
4
10 9 6 35
Sample Output
3 数字有10000个，暴力肯定要炸,但是数字范围只有 1000 ，那么我们可以去重后计数利用乘法原理再算。这样暴力的话就只有10^6了,1要特判（2016湘潭赛有个题很像）
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int num[];
int gcd(int a,int b){
return b==?a:gcd(b,a%b);
}
int main()
{
int tcase,n;
int a[];
scanf("%d",&tcase);
while(tcase--){
memset(num,,sizeof(num));
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+,a++n);
num[a[]]++;
int k=;
for(int i=;i<=n;i++){
if(a[i]==a[i-]){
num[a[i]]++;
continue;
}
a[++k] = a[i];
num[a[i]]++;
}
long long ans=;
for(int i=;i<=k;i++){
for(int j=;j<=i;j++){
if(gcd(a[i],a[j])==&&a[i]!=a[j]){
ans+=(long long)num[a[i]]*num[a[j]];
}else if(a[i]==&&num[a[i]]>){
ans+=num[a[i]]*(num[a[i]]-)/;
}
}
}
printf("%lld\n",ans);
}
return ;
}