题解 | #最大公约数#

#include<iostream>

using namespace std;

/*
* a,b最大公约数g --> b, a mod b 最大公约数
* 不断缩小数据规模
* 直到缩小成求某个非零数与零的最大公约数
* 非零数即为所求
*/

int GCD(int a, int b) {
    while (a != 0 && b != 0) {
        return GCD(b, a % b); //每次要交换两个位置，否则会陷入死循环
        //其实条件只要b!=0就可以，因为如果a=0,b!=0;下一轮就是a=b!=0,b=a%b=0
        //用递归是个好思想
        //不能mod 0
    }
    return a + b;
}

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d\n", GCD(a, b));
    }
}

递归很好用的！