乘法逆元

摘要：
为什么引入乘法逆元？
乘法逆元的定义
将除法转换为乘法，就可以用分配律将大数拆成小数再取模
问：如何求乘法逆元x呢？
方法：费马小定理，扩展欧几里得，线性递推等

乘法逆元

费马小定理

证明

费马小定理

举例

代码实现

#include <iostream>
typedef long long ll;

//快速幂取模
ll fast_pow(ll a, ll b, ll p){
    //a^b%p
    ll ans = 1;
    while(b){
        if(b & 1){
            //若b是奇数(b%2 == 1),则ans单独乘a，b-=1变成偶数
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;//(b/=2)b减半
    }
    return ans;
}
//费马小定理求逆元 x = a^(p-2) % p;(p必须是质数)
ll get_inv(ll a, ll p){
    return fast_pow(a, p-2, p);
}

扩展欧几里得

欧几里得

扩展欧几里得

举例

代码实现

#include <iostream>
void exgcd(const int a, const int b, int &g, int &x, int &y){
    if(b == 0){ g = a; x = 1; y = 0;}
    else {
        exgcd(b, a%b, g, y, x);
        y -= x * (a/b);
    }
}

int get_inv(const int a, int p){
    int g, x, y;
    exgcd(a, p, g, x, y);
    return (x%p + p) % p;
}

线性求逆元

推导

代码实现

int inv[MAXN];
inv [1] = 1;
for(int i = 2; i <= n; i++){
    inv[i] = -(p / i) * inv[p % i];
    inv[i] = (inv[i] % p + p) % p;
}