計算模逆元與一些常用的競賽數學
輾轉相除法
輾轉相除法是求兩數最大公因數比較常用的演算法。
int gcd(int x, int y){ return (x == 0) ? y : gcd(y % x, x); }
int gcd(int x, int y){ return __gcd(a, b); } 對於任意兩數x和y我們可以把他的最大公因數寫成gcd(x, y)，當y大於x時以下式子是永遠成立的，因為gcd(x, y) * k = x 和 gcd(x, y) * r= y的話那gcd(x*y) * (r - k) = y - x，在gcd(x, y)是x和y的最大公因數下gcd(x, y)仍然是y - x和x的最大公因數。假設y - x和x的最大公因數大於gcd(x, y)的話，那y - x 和 x會同時也可以被新的最大公因數相除，那gcd(x, y)就不會是最大公因數了。
而由上述的等式我們可以知道如果今天一直將y - x直到y小於x後他還是原本的解，那我們可以一直將兩個數互相連續的相減直到某數等於0時另一數就會是最大公0因數了，而連續相減我們可以利用mod(%)取餘數的符號來取代，因而衍生出上述程式碼。
擴展歐基里德
接下來終於要來講模逆元了，首先我們先定義以下符號
而b就是我們要求的模逆元，a和n則是任意數字但是必須互值，不然不會有a*b在mod n的情況是1。
我們假設對於認識整數x1和x2，a1*x1 + a2*x2 = gcd(x1, x2)，這種情況下a1和a2必定有解。那我們也可以假設a*x+n*y = gcd(a, n)，a和n由上圖定義，那只要快速求出x和y的解後就可以得出x是a的模逆元了。
而這時拿出我們的輾轉相除法來看一下，我們假設我們要求gcd(a, n)我們會去求gcd(n%a, a)。假設我們得知了x2和y2，我們就可以快速推出x和y了。
所以我們就一直遞迴搜尋等到某次n’%a’為0時a’就會是輾轉相除的答案也就是gcd(a, n)這時我們使得那次的x’=0，y’=1然後在開始回推原本的x和y。而回推公式參考如下
參考程式碼如下
費馬小定理
根據費馬小定理
所以
因此a的p-2次方就是a的模逆元，不過這只適用於a和p互質的狀況下並且p是質數，而且通常在競賽上p會是一個非常大的質數所以實作上要用快速冪來進行次方運算。
線性遞推
假設
所以在mod p 是有意義的情況下
第三行的推導是因為元數乘模逆元要在mod同數字的情況下要相等。
程式碼如下
(n - n/a)%n 就是在計算q但因為他是負號在mod運算裡面會是(-(n / a) + mod ) % mod，然後移項而得。
總結
以速度來說線性遞推<擴展歐基里德<費馬小定理，但是其實他們速度並不會真得差到很多要卡掉是有一定難度的(這邊舉一個卡掉的毒瘤題目洛谷P3811)，至於應用的話費馬和線性遞推都必須是要mod質數的情況下才能用而擴展歐基里德則是只要互質就好是比較有彈性的。