n次剩余O(logp)做法

$n$ 次剩余是这样的：

给你三个正整数 $a,n,p$，你需要求出一个 $b$，使得 $a\equiv b^n\pmod p$

考虑两边同时进行 $n$ 在 $\varphi(p)$ 意义下的逆元次方，那么此时这个式子变成了

那么此时只需要一个快速幂即可解决问题，时间复杂度 $O(\log p)$。

这种做法时间复杂度十分优秀，并且适用性广泛，只需要保证 $\varphi(p)$ 为质数即可，甚至不需要保证 $p$ 为质数。