题解 | #最大公约数#

#include <iostream>
using namespace std;

//辗转相除法求最大公约数
/*
辗转相除法原理：1. 不妨设a>b，则a与b的最大公约数=其中较小值（b）与a/b的余数（a%b）
               的最大公约数。
               2. 若a/b的余数（a%b）==0，则a与b的最大公约数为b。
*/
int gcd1(int a, int b) {
    if (b == 0)
        return a;
    /*
    若a>b，则直接适用于辗转相除法；若a<b，则此处return调用的gcd适用于辗转相除法（∵a%b=a<b）
    */
    return gcd1(b, a % b);
}

//更相减损法求最大公约数
/*
更相减损法原理：1. 不妨设a>b，则a与b的最大公约数=a-b与a（或b）最大公约数
               2. 若a-b==0，则a与b的最大公约数为a（或b）（∵a==b）
*/
int gcd2(int a, int b) {
    if (b == 0)
        return a;
    /*
    若a>b，则直接适用于更相减损法；若a<b，采用取绝对值的方法一样适用更相减损法。
    如：49 14 --> 14 35 --> 35 21 --> 21 14 --> 14 7 --> 7 7 --> 7 0
    14 49 --> 49 35 --> 35 14 --> 14 21 --> 21 7 --> 7 14 --> 14 7 --> 7 7 --> 7 0
    */
    return gcd2(b, abs(a - b));
}

//暴力遍历法
int gcd3(int a, int b){
    int n = a>b?a:b;
    while (a%n!=0||b%n!=0)
        n--;
    return n;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        cout << gcd3(a, b);
    }
}