【算法与数据结构】——乘法逆元

落日映苍穹つ 2022-09-04 04:53 172阅读 0赞

# 定义 #

若在mod p意义下，对于一个整数a，有a\*b≡1(mod p)，那么这个整数b即为a的 乘法逆元，同时a也为b的乘法逆元  
一个数有逆元的充分必要条件是gcd(a,p)=1，此时a才有对p的乘法逆元

# 逆元的作用 #

首先对于除法取模不成立，即 ( a / b ) m o d    p ≠ ( a m o d    p / b m o d    p ) m o d    p (a/b) \\mod p \\neq (a \\mod p / b \\mod p) \\mod p (a/b)modp=(amodp/bmodp)modp。

显然数学家们是不能忍受这种局面的，他们扔出了“逆元”来解决这个问题。

因为取模运算对于乘法来说是成立的，逆元就是把除法取模运算转化为乘法取模运算  
(a/b)%p=m -------- 1  
假设存在一个数x满足  
a\*x%p=m ------- 2

由模运算对乘法成立，对1式两边同时乘以 b ，得到：a%p=(m(b%p))%p  
如果 a 和 b 均小于模数 p 的话，上式可以改写为：a =bm%p  
等式两边再同时乘以 x, 联立2式比较得到:ax%p=m%p=xbm%p  
因此可以得到：bx%p=1

哎，x是b的逆元呀（x 在模运算的乘法中等同于 1/b, 这就是逆元的意义）  
由以上过程我们看到，求取 (a/b)%p 等同于 求取 a∗(b的逆元)%p。 因此，求模运算的除法问题就转化为就一个数的逆元问题了。

# 求逆元的方法 #

因为在算法竞赛中模数p总是质数，所以可以利用费马小定理 ：  
 b p − 1 m o d    p = 1 b^\{p−1\}\\mod p=1 bp−1modp=1  
可以直接得到  
所以 b p − 2 b^\{p-2\} bp−2即为b在 mod p 意义下的逆元

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);
    }

还可以利用扩展欧几里德算法

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