欧拉定理,费马小定理

费马小定理:

$$a^{p-2}\equiv a^{-1}\mod p$$

欧拉定理/拓展欧拉定理:

$$a^b\equiv\begin{cases}a^{b\mod \varphi(p)}&\gcd(a,p)=1\\ a^b&\gcd(a,p)\neq1,b<\varphi(p)\\ a^{b\mod\varphi(p)+\varphi(p)}&\gcd(a,p)\neq1,b\ge\varphi(p)\end{cases}\mod p$$

第二行的意思是不能降幂了(欧拉定理推出来的指数比原来还大不是我们想要的)

一个小技巧

假设你要算

$$\frac ab\mod p$$

其中 $a$ 是一个非常大的数字,比如说 $a$ 要快速幂才能算出来,同时 $p$ 不是质数,意味者用c++没有现有库的情况下较难算出逆元,此时可以扩大模数:

把 $p$ 扩大成 $bp$ ,然后 $a$ 快速幂模 $bp$ ,最后结果直接除掉 $b$ 即可.

质数专题

总结一下什么时候能直接使用定理/函数,什么时候不可以.

模数随意使用

快速幂

模数互质时随意使用

exgcd

模数必须是质数

费马小定理