1756: Prime

Submit Page Summary Time Limit: 3 Sec Memory Limit: 128 Mb Submitted: 281 Solved: 69

Description

如果a,b的最大公约数是1，说明a,b是一对互素的数，给定你n个数字，希望你找出互素的数的对数

Input

第一行输入一个正整数T，表示数据组数

每组数据第一行输入一个正整数n，表示数字的个数(n<=10000)

接下来一行输入n个正整数，每个数字大小不超过1000。

Output

输出互素的数的对数

Sample Input

Sample Output

Hint

Source

3901130321

题解：数字大小最大就是1000 开一个数组保存每一个数字出现的次数

然后从1开始枚举判断1-2 1-3 1-4 ；；；1-999 1-1000 2-3 2-4 ；；；；n-1 - n

是不是互素如果是就加上

 #include <iostream>

 #include <stdio.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <cstring>

 #include <math.h>

 using namespace std;

 int a,num[];

 int gug(int x,int y)

 {

     if(x%y==)return y;

     return gug(y,x%y);

 }

 int main()

 {

     int t,n;

     scanf("%d",&t);

         while(t--)

         {

             for(int i=; i<; ++i)

             {

                 num[i]=;

             }

             scanf("%d",&n);

             for(int i=; i<n; ++i)

             {

                 scanf("%d",&a);

                 num[a]++;

             }

             int ans=;

             if(num[]>)ans+=num[]*(num[]-)/;

             for(int i=; i<; ++i)

             {

                 ans+=num[]*num[i];

                 for(int j=i+; j<=; ++j)

                 {

                     if((num[j]!=)&&(gug(j,i)==))

                         ans+=num[i]*num[j];

                 }

             }

             ans+=num[]*num[];

             printf("%d\n",ans);

         }

     return ;

 }

巴特西

csu 1756: Prime