辗转相除法

什么是辗转相除法

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。

From Baidu

辗转相除法递归式

gcd(a,b) = gcd(b,a mod b)

证明

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b

假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r

因此d也是b,a mod b的公约数

假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。

进而d|a.因此d也是a,b的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

上代码

#include<bits/stdc++.h>
using namespace std;

int gcd(int m,int n)
{
    int r;
    while(n > 0)
    {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int main(void)
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}