乘法逆元

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

乘法逆元

费马小定理证明

费马小定理

举例

代码实现

#include 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 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;}