P5668 【模板】N 次剩余

你需要解方程 $x^n\equiv k\pmod m$，其中 $x\in [0,m-1]$。

无

无

对于 $100 \%$ 的数据，$1\le T\le 100$，$1\le n\le 10^9$，$0\le k \lt m\le 10^9$。 设 $m$ 的唯一分解形式为 $m=\prod_{i=1}^s p_i^{q_i}$，保证方程 $x^n\equiv k\pmod{p_i^{q_i}}$ 在 $[0,p_i^{q_i})$ 中的解数 $\le 10^6$。