逆元的幾種求法

1、快速幂直接求（要求取模的數為質數）

由費馬小定理可得，如果p為質數，則a^(p-1)%c=1=a*a^(p-2)%c;

如果a*b%mod=1;

則a為b的逆元，b也為a的逆元。

a的逆元為a^(mod-2).

ll pow_mod(ll a,ll b)

{

  ll res=1;

  while(b)

{

  if(b&1) res=res*a%mod;

  b=b>>1;

a=a*a%mod;

}

return res;

}

ll inv = (a,mod-2);

2、擴充歐幾裡得求逆元

a*b%mod=1;

a*b+k*mod=1;

如果a與mod互質則存在niyuan，否則不存在。

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(b==0)

    {

        x=1; y=0;

        return a;

    }

    ll t=exgcd(b,a%b,x,y);

    ll xx=x;

    x=y;

    y=xx-a/b*y;

    return t;

}

ll getinv()

{

    ll x,y;

    ll gg = exgcd(a,mod,x,y);

    if(gg==1) return (x%mod+mod)%mod;

    else -1;//無逆元

}

3、線性遞推求逆元

void getInv(ll mod)

{

    inv[1]=1;

    for(int i=2;i<mod;i++)

        inv[i]=(mod-mod/i)*inv[mod%i]%mod;

}