逆元

什么是逆元？

乘法逆元：

• 模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互质。

  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;