问题的核心就在于求两个数的最大公约数。套用最大公约数模板即可。
题目描述：给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
输入：输入有多组，每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。 当n=0时，程序结束，不需要处理这组数据。
输出：每行输出最简真分数组合的个数。
样例输入： 7 3 5 7 9 11 13 15 3 2 4 5 0 样例输出： 17 2 来源： 2012年北京大学计算机研究生机试真题 //注：最小公倍数为两数乘积/最大公约数 #include <cstdio> #include <algorithm> #define MAXSIZE 610 using namespace std; int gcd(int a,int b){ int temp; if (a<b){ temp=a; a=b; b=temp; }//if a<b,swap a and b //process while (a&&b){ temp=b; b=a%b; a=temp; } //output return a; } int main(){ int n,count; int buf[MAXSIZE]; while (scanf("%d",&n),n){ //initiate count=0; //input for (int i=0;i<n;i++){ scanf("%d",&buf[i]); } //sort sort(buf,buf+n); //process for (int i=0;i<n-1;i++){ for (int j=i+1;j<n;j++){ if (gcd(buf[j],buf[i])==1){ count++; } } } //output printf("%d\n",count); } return true; }