九度oj 题目1465：最简真分数

题目描述：: 给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

输入：: 输入有多组，每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。
当n=0时，程序结束，不需要处理这组数据。

输出：: 每行输出最简真分数组合的个数。

样例输入：

7

3 5 7 9 11 13 15

3

2 4 5

0

样例输出：

17

2

此题两两选择，若最大公约数为1，则是最简真分数

代码如下

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 int num[];

 int calGCD(int a, int b) {

     int sum = a + b;

     a = max(a, b);

     b = sum - a;

     if (b == ) {

         return a;

     }

     return calGCD(b, a%b);

 }

 int main() {

     int    n;

     while (scanf("%d", &n) != EOF && n != ) {

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

             scanf("%d", &num[i]);

         }

         int ans = ;

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

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

                 if (calGCD(num[i], num[j]) == ) {

                     ans++;

                 }

             }

         }

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

     }

     return ;

 }

注意求最大公约数的代码，可以写的十分简洁，

辗转相除法

 int gcd(int a, int b) {

     if (b == ) return a;

     return gcd(b, a%b);

 }

巴特西

九度oj 题目1465：最简真分数

最新文章

热门文章