算法学习——逆元

复习逆元……

逆元

求法：

　　1，快速幂
　　　　根据费马小定理有\(a^{p - 1} \equiv 1 \quad (mod \quad p)\),把左边拆开一下得到
　　　　\[a \cdot a^{p - 2} \equiv 1 \quad (mod \quad p)\]
　　　　因此\(a^{p - 2}\)为\(a\)在\(mod \quad p\)意义下的逆元，快速幂即可。
　　2，线性求逆元

    inv[i] = (p - p / i) * inv[p % i] % p;

　　不会证明，强行黑盒。
　　3，扩展欧几里得
　　　　相当于求\(x\)满足\(ax \equiv 1(mod \quad p)\).
　　　　\(ax \equiv 1 + mp(mod \quad p)\)
　　　　\(ax - mp \equiv 1 (mod \quad p)\)
　　　　相当于求解一个二元一次方程，所以直接套扩欧。

void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b) d = a, x = 1, y = 0;
    else exgcd(b, a % b, d, y, x), y -= x * (a / b);
}

LL inv(LL a, LL p)//a在模p意义下的逆元
{
    LL d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x + p) % p : -1;
}//-1表示没有，此为伪代码，不一定可以过编译。。。。。