$$求解x^nequiv a(\%P)，其中P是质数,0leq x<P$$
设$g$是$P$的原根
那么$g^0,g^1,...,g^{P-2}$和$1,2,...,P-1$是一一对应的。
令$x=g^y$,$a=g^t$。
其中解$a=g^t$可以用离散对数，如果$P$不是很大的话，我们也可以用一个map存下$g^0,g^1,...,g^{P-2}$，然后在map中查找即可。
那么则有：
$$g^{y imes n} equiv g^t (\%P)$$
因为$g^0,g^1,...,g^{P-2}$和$1,2,...,P-1$是一一对应的，所以原问题转化成：
$$n imes y equiv t (\%P-1)$$
很好，变成解线性方程。