首页 > 代码库 > 欧几里得定理及扩展
欧几里得定理及扩展
我们都知道欧几里得算法是用来快速求两个数的最大公约数的算法,效率较高: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 }
要证明上述算法的正确性,我们就是证明如下定理的正确性:
定理:设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),那么我们可以递归求出X1 , Y1 满足:
B*X1 + (A%B)Y1 == Gcd(B, A%B) == Gcd(A, B)。
把A%B化简可得:
B*X1 + (A-A/B*B)*Y1 == Gcd(A, B)----->
B*X1 + A*Y1 - A/B*B*Y1 == Gcd(A, B) ------>
A*Y1 + B*(X1 - A/B*Y1 ) == Gcd(A, B)
所以推出:X = Y1
Y = X1 - A/B * Y1
代码如下:
#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;}
扩展欧几里德算法的应用主要有以下三方面:
(1)求解不定方程;
(2)求解模线性方程(线性同余方程);
(3)求解模的逆元;
参考资料:《ACM国际大学生程序设计竞赛算法与实现》俞勇 主编
《离散数学》John.Dossy Ablert.D.Otto著,原书第5版。
欧几里得定理及扩展