歐幾里得演算法 - WiwiHo 的競程筆記

實作上可以用迴圈，常數比較小，不過在C++ 裡不用自己寫，可以用 __gcd(a,b) 。

擴展歐幾里德演算法. 擴展歐幾里德演算法用來求 的整數解。

貝祖定理：. WIWIHO的競程筆記 我教過的課 雜項 複雜度 前置處理器 前綴和與差分 輸入輸出 I/OStream StringStream 輸入輸出優化 數字與位元 進位制 整數與浮點數 位元運算 基礎資料結構 類陣列容器 LinkedList 動態規劃 DP優化 Aliens優化 數學 歐幾里得演算法 快速冪 質數與因數 幾何 向量 向量應用 凸包 進階資料結構 SparseTable 線段樹 樹狀數組 根號 根號分塊 莫隊算法 字串 最長迴文子字串 歐幾里得演算法 歐幾里德演算法也叫輾轉相除法，用來求，它運用了一個性質： 對於，（）。

Proof. ，所以、的公因數和、是一樣的。

從這個性質可以推出，遞迴直到。

因為，所以每過兩次會變小至少一半（），得出這個演算法的時間複雜度是。

12345678intgcd(inta,intb){while(b>0){intt=a%b;a=b;b=t;}returna;} 實作上可以用迴圈，常數比較小，不過在C++裡不用自己寫，可以用__gcd(a,b)。

擴展歐幾里德演算法 擴展歐幾里德演算法用來求的整數解。

貝祖定理： 對於整數，有解若且唯若。

由此可知只要不是的倍數就無解。

有解的話，令，可以先找的解，擴展歐幾里德演算法的作法是嘗試從輾轉相除法的遞迴式，做出一個長得差不多的式子： 得出、，所以先求就可以算出，終止條件一樣是當時，回傳即可。

12345piiexgcd(inta,intb){if(b==0)returnmp(1,0);piians=exgcd(b,a%b);returnmp(ans.S,ans.F-a/b*ans.S);} 最後得到的答案只要乘上倍，就可以變成的答案。

其他的解 擴展歐幾里德演算法只會拿到其中一組解。

先來看看兩組解會有什麼關係：有兩組整數解、，我們知道 因為和互質，因此、，也就是說有了一組解後，其他解都可以寫成，。

負數的狀況 這裡有一些小小細節，因為係數常常有可能是負的，所以特別討論一下負數的狀況。

在上面的式子裡面，寫的都是，但是程式碼裡的a%b實際上是a-a/b*b，而a/b是向零取整而非向下取整。

在不同的除法（向下、向下、向零）定義下，gcd(a,b)給出的結果正負會不一樣。

要避免這個問題發生，就要確保gcd和exgcd的遞迴過程完全一樣。

如果好好照上面那樣寫，並且算用的是__gcd就不會出任何問題，但是如果你在exgcd不小心把a/b變成向下取整，還繼續用__gcd就會出事了。

如果不喜歡有負數的話，可以把負號移到變數上，例如可以變成。

解的範圍 另外還有溢位的問題，事實上可以不用擔心運算過程發生溢位。

因為貝祖定理其實還告訴我們： 一定存在恰兩組整數解滿足、，而且擴展歐幾里德演算法得出的是其中一組。

所以不只可以知道運算過程數字都會保持在一個範圍內，而且還可以知道如果你想要拿到最小正數解之類的，只要把得到的解移動幾次就可以了。

WiwiHo 2022-07-17 Expandall Backtotop Gotobottom