P5668 【模板】N 次剩余

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

第一行正整数 $T$ 为数据组数。 每组数据三个正整数 $n,m,k$。

每组数据一或两行： 第一行为不同解的个数 $c$。 若 $c\neq 0$，接下来第二行共 $c$ 个整数，升序输出所有可能解，空格隔开。 数据保证 $\sum c_i \le 10^6$。

对于 $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$。