【模板】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$。
输入输出样例
输入样例 #1
2
3 531441 330750
5 304128 1
输出样例 #1
27
264 19947 39630 59313 78996 98679 118362 138045 157728 177411 197094 216777 236460 256143 275826 295509 315192 334875 354558 374241 393924 413607 433290 452973 472656 492339 512022
5
1 82945 138241 165889 193537
说明
对于 $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$。