当前位置 博文首页 > Hi_jiaxinwei的博客:【逆元】

    Hi_jiaxinwei的博客:【逆元】

    作者:[db:作者] 时间:2021-09-21 15:08

    逆元(inv)

    1.什么是逆元

    当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:

    设c是b的逆元,则有b*c≡1(mod m);

    则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);

    即a/b的模等于a*b的逆元的模;

    逆元就是这样应用的;


    2.求逆元的方法

    (1).费马小定理

    ? p? 是素数的情况下,对任意整数? x? 都有? xpx(mod)p? 。?
    如果? x? 无法被? p? 整除,则有? xp?11(modp)? 。?
    可以在? p? 为素数的情况下求出一个数的逆元,?

    下一篇:没有了