(n) 次剩余
你需要解方程 (x^nequiv kpmod m)，其中 (xin [0,m-1])。
保证解数不超过 (C=10^6)
(1le n,m,kle 10^9)
(k<m)
Sol
（1）(m) 是奇质数
此时 (m) 有原根，两边取对数得 (nyequiv b pmod {m-1})，使用 ( ext{exgcd}) 可以求出 (y) 在 ([0,m-1]) 的解。
（2）(m=p^e) , (p) 是奇质数。
令 (k\%m ightarrow k) 然后分三种情况讨论如下
1、(k=0)
显然当且仅当 (p^{lceil frac e n ceil}) 时等式能成立，故直接枚举 (p^{lceil frac e n ceil}) 的倍数即可。
2、((k,p^e)=1)
取对数得 (nyequiv b pmod{varphi(p^e)})
这样的方程有解必须有 (gcd(n,varphi(p^e)) mid b)
然后依然可以使用 ( ext{exgcd}) 求解，然后再用指标算出 (x=g^y)。
3、((k,p^e)> 1)
我们设 (k=c imes p^j ((c,p)=1))
这样的方程有解必须有 (n mid j)
然后我们除去 (p^j) ：(displaystyle left(frac{x}{p^{frac{j}{n}}} ight)^nequiv cpmod{p^{e-j}})
换元 (u=frac{x}{p^{frac{j}{n}}})，(u^nequiv c pmod{p^{e-j}})，此时和第 2 种情况一模一样，我们套用之前方法求解。
此处有重大坑点，先跳过。
（3）(m=2^d)
因为要输出所有解，解的个数不多，可以倍增，那么它在模 (2^{k-1}) 情况下的所有解 (x)，如果还要在 (2^k) 成立，必定是 (x) 或 (x+2^{k-1})。
我们对于每一个 (x) 检查一下就好了，然后可以 bfs 出所有解。
最终求解
综上，我们对于一个任意正整数 (m)，只要对其的唯一分解形式 (m=p_1^{q_1}p_2^{q_2}dots) 的每个质数进行求解即可，
最后跑一遍 DFS 枚举模每个 (p^q) 意义下的值，用 CRT（中国剩余定理）合并即可。
许多坑点
1、对 (p^k) 求原根，check 的时候要用 (varphi(p^k)) 而不是直接 (p^k-1)
2、在原式中 (x) 的取值范围是 ([0,p^e))，那么 (y=frac{x}{p^{frac{j}{n}}}) 的取值范围就是 ([0,p^{e-frac{j}{n}}))；
可是在后一个式子中 (y) 的取值范围变成了 ([0,p^{e−j}))！！
因此我们最后的解的个数需要扩大 (p^{j−j/n}) 倍，我们枚举 ([0,p^{e−j})) 中的解向后不断扩展即可。
3、你需要一个正确的 BSGS 板子
4、正确的写法对于任何一个解的 vector 都不需要 unique 的，如果求出大量重复的解可能会被卡掉。