ZJUTOJ-1347-最大公约数

发表于 | 分类于 | 阅读次数

根据读入的两个正整数，计算他们的最大公约数，数据有多组。

Input:

第一行是一个正整数 n (1<=n<=50),接下来n行每行包括两个正整数 a 和 b (1<=a,b<=10000);

Output:

每行输出形式为 Case t: x ，其中 t 从 1 到 n ，x 为运算答案，共 n 行。

Sample Input:

1
2
3
4
5
6
5
20 494
2172 5298
3789 54
3065 7899
3294 5967

Sample Output:

1
2
3
4
5
Case 1: 2
Case 2: 6
Case 3: 9
Case 4: 1
Case 5: 27

Solve:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
int main() {
    int n;
    while(cin >> n) {
        int matrix[n][2];
        int res[n];
        for(int i = 0; i < n; i++) {
            int min = 0;
            cin >> matrix[i][0] >> matrix[i][1];
            int a = matrix[i][0];
            int b = matrix[i][1];
            if(a < b) {
                min = a;
            } else {
                min = b;
            }
            for(int k = 1; k < min; k++) { // 枚举法
                int ret;
                if(a % k == 0) {
                    if(b % k == 0) {
                        ret = k;
                    }
                }
                res[i] = ret;
            }
        }
        for(int j = 0; j <  n; j++) {
            cout << "Case " << j+1 << ": " << res[j] << endl;
        }
    }
    return 0;
}

/*
// 辗转相除法
while( b!=0 ) {
        t = a%b;
        a = b;
        b = t;
    }
    printf("gcd=%d\n", a);
*/

0%