逆元 get ！

· · 个人记录

求法：

前排提示：

无特别说明，p 是素数

1.扩欧

∵ a \times a^{-1}\ \%\ p = 1

∴ a \times a^{-1} - k * p = 1

设 a^{-1} = x\ ,\ k = y\ ,\ p = b

∴ ax + by = 1

用扩欧求 x ，即 a 的逆元

2.费马小定理

∵ a^{(p-1)}\ \%\ p = 1

∴ a \times a^{(p-2)}\ \%\ p = 1

∴ a^{-1} = a^{(p-2)}

再结合快速幂，就可求出 a^{-1}

补充： 大素数判定

如果 ( a \times a^p - 2 ) \% p = 1 成立，

**3.递推求逆元** 设 $p = t \times i + k

∴ t = \lfloor\dfrac{p}{i}\rfloor\ ,\ k = p\%i

∴ t \times i + k ≡ 0 (\%p)

∴ (-t) \times i ≡ k (\%p)

两边同除 i * k：

(-t) \times k^{-1} ≡ i^{-1} (\%p)

等效替代一下：

(p-\lfloor\dfrac{p}{i}\rfloor)\ \times (p\%i)^{-1}\ = i^{-1}

传送门

int main(void)
{
    cin >> n >> p;
    inv[1] = 1;
    cout << '1';
    puts("");
    for(int i=2;i<=n;i++)
    {
        inv[i] = (p-p/i)*inv[p%i]%p;
        cout << inv[i];
        puts("");
    }
    return 0;
}

补充：递推求阶乘逆元

∵ m! = \ \ (m - 1)! \times m

∴ \dfrac{m!}m = (m - 1)!

∴ \dfrac m{m!} = \dfrac 1{(m - 1)!}

∴ m!^{-1} \times m = (m-1)^{-1}

由费马小定理或扩欧求出 m!^{-1} ， 然后就可以递推得到。