算法学习（三）——逆元

当运算时需要求模的时候，可以直接做的有+-*但是不满足/

而逆元就是通过某种运算来达到求(a/b)%p的结果

当 $b*c ≡ 1$ (mod p)时，

有 (a / b) % p = (a / b * b * c) % p = (a * c) % p

这里c就是b关于p的逆元

那么如何求c呢

费马小定理

当p为素数时，有 $a^p$ ≡ a(mod p)

故有$a^p$ ≡ 1(mod p)

因此a关于p的逆元就是$a^{p-2}$

这个幂可以使用快速幂来得出

扩展欧几里得算法

对于不完全为0的非负整数a,b，必存在整数x,y，满足ax+by=gcd(a,b)

因此，求a*x≡1(mod p)

即求ax+py=1=gcd(a,b)/gcd(a,b)

也就是先求出ax+py=gcd(a,b)

然后x=x/gcd(a,b)即可

注意：x可能为负的，需要x=x+p

typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y)    //这是扩展欧几里得
{
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll t = exgcd(b, a%b, x, y);
    ll tmp = y;
    y = x - a / b * y;
    x = tmp;
    return t;
}

k = exgcd(k ,p ,x ,i);
if(x < 0) x += p;                     //防止x为负
x = x / k;

搬运自CSDN：https://blog.csdn.net/yueyue200830/article/details/85334843