歐幾裡德算法又稱輾轉相除法,用于計算兩個整數a,b的最大公約數。
基本算法:設a=qb+r,其中a,b,q,r都是整數,則gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。
遞歸版算法:
1 int gcd(int a,int b)
2 {
3 if(b==0)
4 return a;
5 return
6 gcd(b,a%b);
7 }
遞歸優化版:
1 int gcd(int a,int b)
2 {
3 return b ? gcd(b,a%b) : a;
4 }
疊代版:
1 int Gcd(int a, int b)
2 {
3 while(b != 0)
4 {
5 int r = b;
6 b = a % b;
7 a = r;
8 }
9 return a;
10 }
擴充歐幾裡德算法
基本算法:對于不完全為 0 的非負整數 a,b,gcd(a,b)表示 a,b 的最大公約數,必然存在整數對 x,y ,使得 gcd(a,b)=ax+by。
證明:設 a>b。
1,顯然當 b=0,gcd(a,b)=a。此時 x=1,y=0;
2,ab!=0 時
設 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據樸素的歐幾裡德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據恒等定理得:x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
上面的思想是以遞歸定義的,因為 gcd 不斷的遞歸求解一定會有個時候 b=0,是以遞歸可以結束。
1 int exgcd(int a,int b,int &x,int &y)
2 {
3 if(b==0)
4 {
5 x=1;
6 y=0;
7 return a;
8 }
9 int r=exgcd(b,a%b,x,y);
10 int t=x;
11 x=y;
12 y=t-a/b*y;
13 return r;
14 }
非遞歸版:
1 int exgcd(int m,int n,int &x,int &y)
2 {
3 int x1,y1,x0,y0;
4 x0=1; y0=0;
5 x1=0; y1=1;
6 x=0; y=1;
7 int r=m%n;
8 int q=(m-r)/n;
9 while(r)
10 {
11 x=x0-q*x1; y=y0-q*y1;
12 x0=x1; y0=y1;
13 x1=x; y1=y;
14 m=n; n=r; r=m%n;
15 q=(m-r)/n;
16 }
17 return n;
18 }
擴充歐幾裡德算法的應用主要有以下三方面:
(1)求解不定方程;
(2)求解模線性方程(線性同餘方程);
(3)求解模的逆元;
1 bool linear_equation(int a,int b,int c,int &x,int &y)
2 {
3 int d=exgcd(a,b,x,y);
4 if(c%d)
5 return false;
6 int k=c/d;
7 x*=k; y*=k; //求得的隻是其中一組解
8 return true;
9 }
1 bool modular_linear_equation(int a,int b,int n)
2 {
3 int x,y,x0,i;
4 int d=exgcd(a,n,x,y);
5 if(b%d)
6 return false;
7 x0=x*(b/d)%n; //特解
8 for(i=1;i<d;i++)
9 printf("%d\n",(x0+i*(n/d))%n);
10 return true;
11 }