欧几里得定理及扩展

article/2025/9/18 11:09:20

　　我们都知道欧几里得算法是用来快速求两个数的最大公约数的算法，效率较高：2O(logn)。

　我们先给出算法的实现：

 1 int gcd_1(int a, int b)
 2 {
 3     if(b==0) return a;
 4     return gcd_1(b, a%b);
 5 }
 6 
 7 int gcd_2(int a, int b)
 8 {
 9     while(b)
10     {
11         int r = a%b;
12         a = b;
13         b = r;
14     }
15     return a;
16 }

View Code

　　要证明上述算法的正确性，我们就是证明如下定理的正确性：

　　定理：设a，b，c，q，都是整数，且b>0。如果有a=b*q+c，那么gcd(a,b)==gcd(b,c)。

　　证明：

　　设 d=gcd(a, b), e=gcd(b, c). 于是存在整数k1, k2, k3, k4，使得a=d*k1, b=d*k2, b=e*k3, c=e*k4.

　　那么 a = b*q+c = e*k3*q+e*k4=e*(q*k3+k4).所以e能整除a,从而e<=d;

　　同理：c=a-b*q=d*k1-d*k2*q=d*(k1-k2*q),所以d能整除c,从而d<=e;综上，推出e==d---->gcd(a,b)==gcd(b,c)。

--------------------------- 分割线 -----------------------------------

　　重点是扩展欧几里德定理，它在解线性同余式和中国剩余定理等很多方面都很有用。

　　给你两个整数A，B让求一组整数解(X,Y)使得 Gcd(A,B)==A*X+B*Y。数论已经证明这组解一定存在。并且我们可以用扩展欧几里得算法求出解。

　　首先给出欧几里得算法的证明过程：

　　我们要求的是使 A*X+B*Y == Gcd(A, B)成立的X,Y值.

　　根据欧几里得算法有：Gcd(A, B)==Gcd(B, A%B)，那么我们可以递归求出X₁ , Y₁ 满足：

　　B*X₁ + (A%B)Y₁ == Gcd(B, A%B) == Gcd(A, B)。

　　把A%B化简可得：

　　B*X₁ + (A-A/B*B)*Y₁ == Gcd(A, B)----->

　　B*X₁ + A*Y₁ - A/B*B*Y₁ == Gcd(A, B) ------>

　　A*Y₁ + B*(X₁ - A/B*Y₁ ) == Gcd(A, B)

　　所以推出：X = Y₁

Y = X₁ - A/B * Y₁

　　代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;__int64 Exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{if(b==0){x=1, y=0;return a;}__int64 ans = Exgcd(b, a%b, x, y);__int64 tp=x;x = y;y = tp - a/b*y;return ans;
}int main()
{__int64 a, b, x,y;while(~scanf("%I64d%I64d", &a, &b)){__int64 ss = Exgcd(a, b, x, y);printf("%I64d, %I64d, %I64d\n", x,y,ss);}return 0;
}