首页 > 代码库 > 欧几里德算法与扩展欧几里德算法

欧几里德算法与扩展欧几里德算法

欧几里得算法就是我们常说的辗转相除法,辗转相除法可以用来求最大公约数,知道最大公约数还可以求最小公倍数。gcd在好像也有库函数__gcd

技术分享
int Gcd(int a, int b)
{
    while(b != 0)
    {
      int r = b;
      b = a % b;
      a = r;
    }
    return a;
}
非递归方法
技术分享
int gcd(int a,int b)
{return b ? gcd(b,a%b) : a;}
递归方法

扩展欧几里得算法是在解决一个什么问题呢,解方程,解二元一次方程的通解。

扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数,此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。by百度百科

技术分享
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
非递归方法
技术分享
int exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}
递归方法

扩展欧几里德算法的应用主要有以下三方面:

(1)求解不定方程;

(2)求解模线性方程(线性同余方程);

(3)求解模的逆元;

欧几里德算法与扩展欧几里德算法