欧几里得算法

计((a, b))为a和b的所有公约数，那么有((a, b) = (b, a \% b))

证明：

计((a, b) = A, (b, a - kb) = B,(a\%b = a - kb,k=[a/b]))

(1)) (ecauseforall x in A,)有(x | a)且(x|b)

( herefore x | (pa + qb),(p,qin Z))

( herefore)有(x|b)且(x|(a-kb))

( hereforeforall x in A)有(xin B)，即(A sub B)

(2)) (ecauseforall x in B,)有(x | (a - kb))且(x|b)

( herefore x|[(a - kb) + kb])

( herefore x|a)

( herefore x|a)且(x|b)

( hereforeforall x in B)有(xin A)，即(B sub A)

由1）2）得(A = B)，所以(max{A} = max{B})

即gcd(a, b) = gcd(b, a % b)

给定n对正整数ai,bi，请你求出每对数的最大公约数。

递归版

#include<iostream>
using namespace std;

int n;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

int main(){
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int a, b;
        cin >> a >> b;
        
        cout << gcd(a, b) << endl;
    }
    
    return 0;
}

迭代版

#include<iostream>
using namespace std;

int n;

int main(){
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int a, b;
        cin >> a >> b;
        
        while(b){
            int t = b;
            b = a % t;
            a = t;
        }
        
        cout << a << endl;
    }
    
    return 0;
}