擴充歐幾裡德算法
先介紹什麼叫做歐幾裡德算法
有兩個數 a b，現在，我們要求 a b 的最大公約數，怎麼求？枚舉他們的因子？不現實，當 a b 很大的時候，枚舉顯得那麼的naïve ，那怎麼做？
歐幾裡德有個十分又用的定理： gcd(a, b) = gcd(b , a%b) ，這樣，我們就可以在幾乎是 log 的時間複雜度裡求解出來 a 和 b 的最大公約數了，這就是歐幾裡德算法，用 C++ 語言描述如下：
由于是用遞歸寫的，是以看起來很簡潔，也很好記憶。那麼什麼是擴充歐幾裡德呢？
現在我們知道了 a 和 b 的最大公約數是 gcd ，那麼，我們一定能夠找到這樣的 x 和 y ，使得: a*x + b*y = gcd 這是一個不定方程（其實是一種丢番圖方程），有多解是一定的，但是隻要我們找到一組特殊的解 x0 和 y0 那麼，我們就可以用 x0 和 y0 表示出整個不定方程的通解：
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t
為什麼不是：
x = x0 + b*t
y = y0 – a*t
那是因為：
b/gcd 是 b 的因子， a/gcd 是 a 的因子是吧？那麼，由于 t的取值範圍是整數，你說 (b/gcd)*t 取到的值多還是 b*t 取到的值多？同理，(a/gcd)*t 取到的值多還是 a*gcd 取到的值多？那肯定又要問了，那為什麼不是更小的數，非得是 b/gcd 和a/gcd ？
注意到：我們令 B = b/gcd ， A = a、gcd ， 那麼，A 和 B 一定是互素的吧？這不就證明了 最小的系數就是 A 和 B 了嗎？要是實在還有什麼不明白的，看看《基礎數論》（哈爾濱工業大學出版社），這本書把關于不定方程的通解講的很清楚
現在，我們知道了一定存在 x 和 y 使得 ： a*x + b*y = gcd ， 那麼，怎麼求出這個特解 x 和 y 呢？隻需要在歐幾裡德算法的基礎上加點改動就行了。
我們觀察到：歐幾裡德算法停止的狀态是： 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
以上就是擴充歐幾裡德算法的全部過程，依然用遞歸寫：
依然很簡短，相比歐幾裡德算法，隻是多加了幾個語句而已。
這就是理論部分，歐幾裡德算法部分我們好像隻能用來求解最大公約數，但是擴充歐幾裡德算法就不同了，我們既可以求出最大公約數，還可以順帶求解出使得： a*x + b*y = gcd 的通解 x 和 y
擴充歐幾裡德有什麼用處呢？
求解形如 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/gcd)*t ，但是想想一下就明白了，gcd = 1，是以寫了跟沒寫是一樣的，但是，由于問題的特殊性，有時候我們得到的特解 x0 是一個負數，還有的時候我們的 m 也是一個負數這怎麼辦？
當 m 是負數的時候，我們取 m 的絕對值就行了，當 x0 是負數的時候，他模上 m 的結果仍然是負數（在計算機計算的結果上是這樣的，雖然定義的時候不是這樣的），這時候，我們仍然讓 x0 對abs(m) 取模，然後結果再加上abs(m) 就行了，于是，我們不難寫出下面的代碼求解一個數 a 對于另一個數 m 的乘法逆元：