乘法逆元初探（擴充歐幾裡得）

LaTeX \LaTeX LATE​X版本~

情境引入

衆所周知，有一個神奇的函數叫做gcd，中文名叫最大公約數

算法極其簡單

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

這種計算gcd的方法往往被稱為輾轉相除，但是，他的學名叫做“歐幾裡得算法”

但是，歐幾裡得這個數學家可隻想用一個gcd來折磨人

于是，他又研究出一個叫做exgcd的東西，學名“擴充歐幾裡得”

例題： 洛谷 P1082同餘方程

求關于x的方程a*x mod b = 1 的最小整數解

問題轉化

我們觀察題目這個等式，他的實質是在求ax+by=1這個等式的最小整數解

這裡 y是我們新引入的某個整數，并且似乎是個負數才對。這樣表示是為了用擴充歐幾裡得算法。我們将要努力求出一組 x,y 來滿足這個等式。

看到這裡，大家可能會有疑問：擴充歐幾裡得是用來求 ax + by = gcd(a,b) 中的未知數的，怎麼牽扯到等于 1 呢？

原理是，方程 ax + by = max+by=m 有解的必要條件是 m mod gcd(a,b)=0。

由最大公因數的定義，可知 a 是 gcd(a,b) 的倍數，且 b是gcd(a,b) 的倍數，

若 x,y都是整數，就确定了 ax + by 是 gcd(a,b) 的倍數，

因為 m = ax + by，是以 m必須是 gcd(a,b) 的倍數，

那麼 m mod gcd(a,b) = 0

可得出在這道題中，方程 ax + by = 1 的有解的必要條件是 1 mod gcd(a,b)=0。是以 gcd(a,b) 隻能等于 1 了。這實際上就是a,b互質

擴充歐幾裡得

擴充歐幾裡得，簡稱擴歐，實在基礎的歐幾裡得算法（gcd）的基礎上實作的

代碼：

# include <cstdio> 
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}
           

最後輸出什麼呢？

當然是x了，但是因為要mod一個數

是以我們要輸出x%b

不對，再好好考慮考慮

x有可能是負數，是以我們要輸出(x+b)%b

大功告成

小結

擴充歐幾裡得是一種非常常用的求逆元的方法

當然，你們有可能會問，你上面講了這麼多，和求逆元沒什麼關系啊

最後輸出的就是逆元啊