逆元


什么是逆元?

乘法逆元:

  • 模p意义下,一个数a如果有逆元x,那么除以a相当于乘以x。
  • 在模n的意义下,a存在逆元的充要条件是**n不等于1,且(a,n)互质。

    怎样求逆元?

  1. 费马小定理(有限制)
    =》p为素数时,a关于mod p的逆元为a^(p-2)mod p。用快速幂模。
  2. 扩展欧几里得算法(普遍适用)
  • 给定模数n,求a的逆元
  • 即ax=1(mod n)
  • =》ax-ny=1
  • 所以可用扩展欧几里得, ax+by=gcd(a,b)求逆元,即求x的值。

    注意:

    存在逆元的判断条件是 a,m互质
    1
    2
    3
    4
    5
    6
    7
    if(gcd(a,m) != 1)       //a,m不互质,则不存在逆元
    cout << "Not Exist" << endl;
    else
    {
    ext_gcd(a, m, x, y);
    LL ans = (x<=0) ? (x%m+m) : x; //有可能x是负数,x要先取模再加
    cout << ans << endl;

文章作者: Rain
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Rain !
  目录