乘法逆元

若$ax\equiv 1\left ( mod \ p \right )$，则称x，a 互为mod p 意义下的逆元

1. 扩展欧几里得算法 $$ax\equiv 1\left ( mod \ p \right )\Leftrightarrow ax+py=1$$ 若$gcd\left ( a,p \right )\neq 1$则无解

void exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b) {x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;	
}

1. 费马小定理
   若p 为质数，则$a^{p}\equiv a\left ( mod \ p \right )$

   $$x\equiv a^{p-2}\left ( mod \ p \right )$$

2. 欧拉定理
   若$gcd\left ( a,p \right )=1$，则$a^{\varphi\left ( p \right )}\equiv 1\left ( mod \ p \right )$

   $$x\equiv a^{\varphi\left ( p \right )-1}\left ( mod \ p \right )$$

3. 线性递推
   设$p=k*i+r$，其中$\left ( r<i,1<i<p \right )$

   $$k*i+r\equiv 0\left ( mod \ p \right )$$

   同时乘上$i^{-1},r^{-1}$，得$k*r^{-1}+i^{-1}\equiv 0\left ( mod \ p \right )$

   $$i^{-1}\equiv k*r^{-1}\left ( mod \ p \right )$$ $$i^{-1}\equiv \left \lfloor \frac{p}{i} \right \rfloor*\left [p\mod i \right ]^{-1}\left ( mod \ p \right )$$