擴充歐幾裡得與乘法逆元

一。歐幾裡得算法

歐幾裡德算法又稱輾轉相除法，用于計算兩個整數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     if(b==0)
4         return a;
5     return 
6         gcd(b,a%b);
7 }      

疊代實作

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= gcd ， b = 0 ，那麼，這是否能給我們求解 x y 提供一種思路呢？因為，這時候，隻要 a = gcd 的系數是 1 ，那麼隻要 b 的系數是 0 或者其他值（無所謂是多少，反正任何數乘以 0 都等于 0 但是a 的系數一定要是 1），這時，我們就會有： a*1 + b*0 = gcd

當然這是最終狀态，但是我們是否可以從最終狀态反推到最初的狀态呢？

假設目前我們要處理的是求出 a 和 b的最大公約數，并求出 x 和 y 使得 a*x + b*y= gcd ，而我們已經求出了下一個狀态：b 和 a%b 的最大公約數，并且求出了一組x1 和y1 使得： b*x1 + (a%b)*y1 = gcd ， 那麼這兩個相鄰的狀态之間是否存在一種關系呢？

我們知道： a%b = a - (a/b)*b（這裡的 “/” 指的是整除，例如 5/2=2 , 1/3=0），那麼，我們可以進一步得到：

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

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

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

    對比之前我們的狀态：求一組 x 和 y 使得：a*x + b*y = gcd ，是否發現了什麼？

    這裡：

        x = y1

        y = x1 – a/b*y1

    以上就是擴充歐幾裡德算法的全部過程，依然用遞歸寫：

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 ans=exgcd(b,a%b,x,y);
10     int t=x;
11     x=y;
12     y=t-a/b*y;
13     return ans;
14 }      

這就是理論部分，歐幾裡德算法部分我們好像隻能用來求解最大公約數，但是擴充歐幾裡德算法就不同了，我們既可以求出最大公約數，還可以順帶求解出使得：

a*x + b*y = gcd 的通解 x 和 y

擴充歐幾裡德算法的應用主要有以下三方面：

（1）求解不定方程；

（2）求解模線性方程（線性同餘方程）；

（3）求解模的逆元；

其中擴充歐幾裡得算法一個重要的應用在求解形如 a*x +b*y = c 的特解，比如一個數對于另一個數的乘法逆元

三。乘法逆元

什麼叫乘法逆元？

    這裡，我們稱 x 是 a 關于 m 的乘法逆元

    這怎麼求？這裡我們利用擴充歐幾裡得算法，等價為： a*x + m*y = 1

    我們發現當gcd(a , m) != 1 的時候是沒有解的，這也是 a*x + b*y = c 有解的充要條件： c % gcd(a , b) == 0

    一般，我們能夠找到無數組解滿足條件，但是一般是讓你求解出最小的那組解，怎麼做？我們求解出來了一個特殊的解 x0 那麼，我們用 x0 % m其實就得到了最小的解了。為什麼？

可以這樣思考：

     x 的通解不是 x0 + m*t 嗎？

    那麼，也就是說， a 關于 m 的逆元是一個關于 m 同餘的，那麼根據最小整數原理，一定存在一個最小的正整數，它是 a 關于m 的逆元，而最小的肯定是在（0 , m）之間的，而且隻有一個，這就好解釋了。

    但是，由于問題的特殊性，有時候我們得到的特解 x0 是一個負數，還有的時候我們的 m 也是一個負數這怎麼辦？

    當 m 是負數的時候，我們取 m 的絕對值就行了，當 x0 是負數的時候，x0% m 的結果仍然是負數（在計算機計算的結果上是這樣的，雖然定義的時候不是這樣的），這時候，我們仍然讓 x0 對abs(m) 取模，然後結果再加上abs(m) 就行了，于是，我們不難寫出下面的代碼求解一個數 a 對于另一個數 m 的乘法逆元：

1 int cal(int a,int m)
 2 {
 3     int x,y,ans,gcd;
 4     gcd=exgcd(a,m,x,y);
 5     if(1%gcd!=0)///無解
 6     {
 7         return -1;
 8     }
 9     x=x*1/gcd;
10     m=abs(m);
11     ans=x%m;
12     if(ans<=0)
13     {
14         ans=ans+m;
15     }
16     return ans;
17 }      

這裡給出一道例題作為乘法逆元的模闆

給出2個數M和N(M < N)，且M與N互質，找出一個數K滿足0 < K < N且K * M % N = 1，如果有多個滿足條件的，輸出最小的。

 Input

輸入2個數M, N中間用空格分隔（1 <= M < N <= 10^9)

Output

輸出一個數K，滿足0 < K < N且K * M % N = 1，如果有多個滿足條件的，輸出最小的。

Sample Input

2 3      

Sample Output

2      

1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 void exgcd(int a,int b,int &x,int &y)
 5 {
 6     if(b==0)///遞歸結束條件
 7     {
 8         x=1;
 9         y=0;
10         return ;
11     }
12     exgcd(b,a%b,x,y);
13     int t=x;
14     x=y;
15     y=t-a/b*y;
16 }
17 
18 int main()
19 {
20     int n,m;
21     int x,y;
22     scanf("%d%d", &m,&n);
23     exgcd(m,n,x,y);
24     while(x<0)
25     {
26         x=x+n;
27     }
28     printf("%d\n",x);
29     return 0;
30 }