欧几里得算法和扩展欧几里得算法(Euclidean_Algorithm and Extended_Euclidean_Algorithm)

一、基本概念

欧几里得算法：又名辗转相除法，计算两个整数a,b的最大公约数。

扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

二、基本性质

gcd函数的基本性质：gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

贝祖定理： 即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

三、算法

欧几里得算法

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

证明：

将a表示为 a=kb+r，则 r=a%b , r=a-kb；

假设d为a,b的一个公约数，则a%d = 0 , b%d = 0  , 又r = a - kb，所以r % d = 0;

整理下：b % d = 0 ， r % d = 0（ (a % b) % d = 0 ）

即 d也是b和a%b的公约数，所以a和b的最大公约数也是b和a%b的最大公约数。

扩展欧几里得算法

已知：a%b=a-(a/b)*b

b*x1 + (a-(a/b)*b)*y1

= b*x1 + a*y1 – (a/b)*b*y1

= a*y1 + b*(x1 – a/b*y1) = gcd

证明：

假设 a>b,

(1)  b=0  gcd(a,b) = a ,  ax = a ,  则x=1，y=0;（这里我还是推荐不把gcd(a,0)理解成最大公约数，而是一个计算机求出来的值）

(2) 假设 ax1+by1=gcd(a,b) (方程一) bx2+(a%b)y2=gcd(b,a%b)（方程二）;由欧几里得算法gcd(a,b) =gcd(b,a%b) 得到，

ax1+by1 = bx2+(a%b)y2，即ax1+by1=bx2+(a-a/b*b)y2 ax1+by1=ay2+b(x2-a/b*y2)

四、代码

欧几里得算法

C++版本一

1. 若 r 是 a ÷ b 的余数, 则

gcd(a,b) = gcd(b,r)

2. a 和其倍数之最大公因子为 a。

#include<iostream>
using namespace std;

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int main()
{
    int a,b;
    cout<<"Please enter two integers:"<<endl;
    cin>>a>>b;
    cout<<a<<" and "<<b<<"'s gcd is："<<endl;
    cout<<gcd(a,b)<<endl;
return 0;
}

C++版本二

1. a ÷ b，令r为所得余数（0≤r＜b）

若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

#include<iostream>
using namespace std;

int gcd(int a,int b)
{
    int temp;
    while(b!=0)
    {
        temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

int main()
{
    int a,b;
    cout<<"Please enter two integers:"<<endl;
    cin>>a>>b;
    cout<<a<<" and "<<b<<"'s gcd is："<<endl;
    cout<<gcd(a,b)<<endl;
return 0;
}

扩展欧几里得算法

C++版本一

#include<iostream>
using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
     if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int x2=x,y2=y;
    x=y2;
    y=x2-(a/b)*y2;
    return gcd;
}

int main()
{
int x,y,a,b;
cout<<"请输入a和b:"<<endl;
cin>>a>>b;
cout<<"a和b的最大公约数:"<<endl;
cout<<exgcd(a,b,x,y)<<endl;
cout<<"ax+by=gcd(a,b) 的一组解是:"<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}

C++版本二

#include<iostream>
using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=a%b;
    int q=(a-r)/b;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        a=b; b=r; r=a%b;
        q=(a-r)/b;
    }
    return b;
}

int main()
{
int x,y,a,b;
cout<<"请输入a和b:"<<endl;
cin>>a>>b;
cout<<"a和b的最大公约数:"<<endl;
cout<<exgcd(a,b,x,y)<<endl;
cout<<"ax+by=gcd(a,b) 的一组解是:"<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}

五、例题

https://codeforces.com/contest/1152/problem/C（题解：https://blog.csdn.net/weixin_43272781/article/details/89513932）

六、参考文章

https://www.cnblogs.com/haveyoueverbeen/p/4502005.html

https://www.cnblogs.com/haveyoueverbeen/p/4612753.html

https://www.cnblogs.com/haveyoueverbeen/p/4612827.html