乘法逆元、更相減損術與輾轉相除法、歐幾裡得算法和拓展歐幾裡得算法

乘法逆元與其計算基礎

本文描述 乘法逆元、更相減損術、輾轉相除法和拓展歐幾裡得算法。由于這幾項内容是互相關聯，可以層次深化的，是以此處放在一起描述。各章節之間存在遞進關系，請看官留心邏輯關聯。

更相減損術與輾轉相除法

兩個算法多用于計算最大公約數，經由拓展方式處理可以用于計算乘法逆元。以下為算法描述：

更相減損術

記數字 A=8，數字 B=4，計算二者的最大公約數。

更相減損術的核心思想是 兩個數既然有最大公約數（gcd），那麼二者必然均由 最大公約數的數倍表示，即 A = k 1 × g c d A = k_1\times gcd A=k1​×gcd， B = k 2 × g c d B = k_2 \times gcd B=k2​×gcd。是以，二者隻要反複互減，最終将化簡至一個 不可分元，即最大公約數。

輾轉相除法

輾轉相除法基于 更相減損術 的邏輯進行描述，依然是兩個數字均為最大公約數的 數倍。兩個數除了是最大公約數的倍數之外，互相之間也可能呈現一定的倍數關系。若有 A = k ′ × B + g c d A = k^{'} \times B + gcd A=k′×B+gcd，此時，二者計算 A % B = g c d A\%B = gcd A%B=gcd即可得到結論。主要依據的規則為:

• g c d ( A , B ) = g c d ( B , A % B ) gcd(A, B) = gcd(B, A\%B) gcd(A,B)=gcd(B,A%B)

  其中，不妨設A>B；

較之于更相減損術每次從兩個數中減去數倍的 gcd，輾轉相除法每次删掉數倍的 k × g c d k \times gcd k×gcd，是以收斂速度快一些。

乘法逆元

以上兩種算法用于描述最大公約數。因為兩個數都是由最大公約數的數倍構成，顯然有:

∃ k 1 , k 2 ∈ Z k 1 × A + k 2 × B = g c d \exist k_1,k_2\in Z\\ k_1\times A + k_2\times B = gcd ∃k1​,k2​∈Zk1​×A+k2​×B=gcd

乘法逆元是對于式子 k 1 × A + k 2 × B = g c d k_1\times A + k_2\times B = gcd k1​×A+k2​×B=gcd一種特殊情況的描述，即 A − 1 × A + k 2 × B = 1 ( m o d    B ) A^{-1}\times A + k_2\times B = 1 (mod\ \ B) A−1×A+k2​×B=1(mod  B)，則 A , A − 1 A, A^{-1} A,A−1互為乘法逆元。定義描述為：

若在mod p意義下，對于一個整數a，有a*b≡1(mod p)，那麼這個整數b即為a的 乘法逆元，同時a也為b的乘法逆元。一個數有逆元的充分必要條件是gcd(a,p)=1，此時a才有對p的乘法逆元。

摘自:https://www.cnblogs.com/-citywall123/p/10673212.html

**提出乘法逆元的主要目的是用于描述特定的餘數值。**假設我們知道：

1. A % d = c A \% d = c A%d=c，其中 c , d c,d c,d已知。
2. 而且 g c d ( B , d ) = 1 gcd(B, d) = 1 gcd(B,d)=1 ，即存在 B 的乘法逆元，使得 B − 1 B % d = 1 B^{-1}B\%d = 1 B−1B%d=1；
3. 那麼對式子放縮可以得到 c × B − 1 B % d = c c\times B^{-1}B\%d = c c×B−1B%d=c;
4. 由此可得 A = c ⋅ B − 1 B + k d A = c\cdot B^{-1}B + kd A=c⋅B−1B+kd，實作了将A表示為B的函數；

是以，當題目中提供一些B的特殊性質的時候，就可以使用題目中提供的條件，利用變量B進行求解。

乘法逆元的計算方法目前常用有兩種，一種是費馬小定理(如下)，一種是拓展歐幾裡得。

費馬小定理認為，p為質數的時候（即特殊情況下），有 b p − 1 % p = 1 b^{p-1}\%p=1 bp−1%p=1，顯然，逆元為 b p − 2 b^{p-2} bp−2。

ll pow(ll a, ll n, ll p)    //快速幂 a^n % p
{
    ll ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

ll niyuan(ll a, ll p)   //費馬小定理求逆元
{
    return pow(a, p - 2, p);
}
           

拓展歐幾裡得算法

歐幾裡得算法用于計算最大公約數，實際上就是輾轉相除法。代碼如下：

int getGCD(int a, int b){
    int gcd = 1;
    if (b == 0){
        gcd = a;
        return gcd;
    }
    // gcd(a, b) = gcd(b, a%b);
    gcd = getGCD(b, a%b);
    
    return gcd;
}
           

拓展歐幾裡得算法可以用于計算乘法逆元。主要使用歐幾裡得算法中的遞推關系：

1. g c d = k 1 ⋅ A + k 2 ⋅ B gcd = k_1 \cdot A+k_2\cdot B gcd=k1​⋅A+k2​⋅B;
2. g c d = k 1 ⋅ B + k 2 ⋅ A % B = k 1 ⋅ B + k 2 ⋅ ( A − A B ) gcd = k_1\cdot B+k_2\cdot A\%B = k_1\cdot B + k_2\cdot (A - \frac{A}{B}) gcd=k1​⋅B+k2​⋅A%B=k1​⋅B+k2​⋅(A−BA​)；
3. 化簡，提出公因式 k 1 , k 2 k_1, k_2 k1​,k2​，得到基于下層遞歸結果計算上層遞歸的遞推算式： k 2 = k 1 k_2 = k_1 k2​=k1​和 k 1 = k 2 × ( A − A B ) k_1=k_2\times(A-\frac{A}{B}) k1​=k2​×(A−BA​)；

void exgcd(ll a, ll b, ll &x, ll &y)    //拓展歐幾裡得算法
{
    if(!b) 
        x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}

ll niyuan(ll a, ll b)   //求a對b取模的逆元
{
    ll x, y;
    exgcd(a, b, x, y);
    return (x + b) % b;
}
           

妥