n次剩余O(logp)做法

· · 休闲·娱乐

给你三个正整数 $a,n,p$，你需要求出一个 $b$，使得 $$a\equiv b^n\pmod p$$ 考虑两边同时进行 $n$ 在 $\varphi(p)$ 意义下的逆元次方，那么此时这个式子变成了 $$a^{\text{inv}(n)}\equiv b\pmod p$$ 那么此时只需要一个快速幂即可解决问题，时间复杂度 $O(\log p)$。 这种做法时间复杂度十分优秀，并且适用性广泛，只需要保证 $\varphi(p)$ 为质数即可，甚至不需要保证 $p$ 为质数。