PTA 7-151 最大公约数

PTA 7-151 最大公约数

分数 10
作者 usx程序设计类课程组
单位 绍兴文理学院

求两个正整数m，n的最大公约数（Greatest Common Divisor，简称GCD）。

输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入2个整数m,n (0

输出格式:
对于每组测试，输出m，n的最大公约数。

输入样例:

2
63 36
20 15
1
2
3

输出样例:

9
5
1
2

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

#include 
#include 
int main(){
    int m, n, T;
    int min_numb, max_numb;
    int consult;    //商
    int remainder;    //余数
    scanf("%d", &T);
    while(scanf("%d %d", &m, &n) != EOF){
        //辗转相除法: 两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数
        min_numb = m > n ? n : m;    //较小的数
        max_numb = m > n ? m : n;    //较大的数
        while(min_numb >= 0 && max_numb >= 0){    //两个数是正数进入循环
            consult = max_numb / min_numb;    //两数的商
            remainder = fmod(max_numb, min_numb);    //两数的余数
            max_numb = consult * min_numb + remainder;    //较大的数=两数的商*较小的数+两数的余数
            max_numb = min_numb;    //将较小的数作为较大的数
            min_numb = remainder;    //将余数作为作为较小的数
            if(min_numb == 0) break;    //如果余数为0, 则跳出循环
        }
        printf("%d\n", max_numb);
    }
    /*辗转相除法 eg: 63 36
        63 = 1 * 36 + 27    //36 27
        36 = 1 * 27 + 9    //27 9
        27 = 3 * 9 + 0    //9 0
        则输出9*/
    return 0;
}
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

解题思路：
step1：首先了解辗转相除法
step2：控制处理到文件尾
step3：算出较小的较大的数
step4：两数为正数进入循环并设置“辗转相除法”的规则
step5：输出并换行

归属知识点：
循环结构