$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

欧几里德算法

结论： $\gcd(a,b)=\gcd(b,a \bmod b)$

证明：
设 $a=bk+c$，显然有$c=a\bmod b$。设 $d \mid a,d\mid b$，则 $c=a-bk,\dfrac{c}{d}=\dfrac{a}{d}-\dfrac{b}{d}k$
由右边的式子可知 $\dfrac{c}{d}$ 为整数，即 $d \mid c$，所以对于 $a，b$ 的公约数也是 $b,a \bmod b$ 的公约数。
反过来也需要证明：
设 $d \mid b,d \mid (a \bmod b)$，我们依旧可得式子：$\dfrac{a \bmod b}{d}+\dfrac{b}{d}k=\dfrac{a}{d}$
因为左边式子显然为整数，故 $\dfrac{a}{d}$ 也为整数，即 $d \mid a$，所以对于 $b,a \bmod b$ 的公约数也是 $a,b$ 的公约数。
既然两式公约数相同，那么最大公约数也会相同。
所以得到式子：$\gcd(a,b)=\gcd(b,a \bmod b)$

完整代码

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int n;
    cin>>n;

    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }

    return 0;
}