什么是逆元?
逆元存在的条件是在取模运算中,一个数的逆元和该数乘积取模后的结果为1,即ax≡1(mod p),称x为a关于p的逆元,其中gcd(a,p)=1。
什么是逆元?a∗x≡1modm,这里x就是a的逆元。逆元有什么用呢?*如果我们要求a/bmodm的值,而a,b很大,设b的逆元为x,这个时候注意到(a/b)∗x∗b=(a/b)modm=a∗xmodm巧妙地把出发转换成了乘法
逆元求法

  1. 扩展欧几里得算法O(logn)
    裴蜀定理:若a,b是整数,且gcd(a,b)=d,那么对于任意的对任意整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。(a,b互质的充要条件是存在整数x,y使ax+by=1.)
    代码:x为a的逆元
    void exgcd(int a,int b,int &x,int &y)
    {
    if(b==0){x=1,y=0;return ;}
    exgcd(b,a%b,x,y);
    ll z=x;
    x=y;
    y=z-y*(a/b);
    return ;
    }
    如果gcd(a,b)=1时,对公式两边同时取模b,则有ax≡1(mod b),所以x为a关于模b的逆元。
  2. 费马小定理
  3. 线性求逆元