欧几里得算法

本文主要是介绍欧几里得算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

　　欧几里得算法：

　　gcd(x,y)=gcd(y,x%y);

　　边界条件：if（y==0）return x;

证明：

　　 我们设gcd(a,b)=d····（1），a=k*b+c····（2），再令a=k1*d,b=k2*d····（3）

　　 由（2）得c=a-k*b····（4），然后将（1）带入（4）得到:c=k1*d-k*k2*d,即c=(k1-k*k2)*d.

　　 这样就说明，a%b有d这个约数，因为开始我们设b也有d这个约数，所以gcd(a,b)是b，a%b的一个公约数。

#include<bits/stdc++.h>
using namespace std;
int a,b;
inline int gcd(int x,int y)
{
    return b?gcd(b,a%b):a;
}
int main()
{
        cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

这篇关于欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！