求$x^A \equiv B\pmod p$的所有$x$

未分类

题意：
给定$A,B,P$，且$P$是质数，求所有满足$x^A\equiv B\pmod P$的$x$.
$(1\leq A,B \leq P-1,2\leq P \leq 10^9)$

1、原根
对一个质数$P$来说，如果正整数$g$满足$g^i \%P(1\leq i < P)$两两不同，那么称$g$是模$P$的一个原根。
质数的最小原根通常都比较小，所以可以通过枚举来计算。
详细的说，枚举一个数$g$，然后枚举$P-1$的所有质因子$v$，如果$g^{(P-1)/v}\%P$均不为$1$，那么$g$就是模$P$的一个原根。

2、离散对数
已知$a,b,P(1< a < P,1\leq b<P)$，且$P$是质数，求解满足$a^n\equiv b \pmod P$的$n$，这种问题被称为离散对数问题。
设$K = \lfloor \sqrt{n} \rfloor$，那么$n$可以被表示成$n = xK+y$，其中$0\leq x \leq K,0\leq y < K$，也就是$a^{xK+y}\equiv b\pmod P$，等价于$a^{xK}\equiv ba^{-y} \pmod P$。那么可以将全部的$a^{xK}\%P$放入哈希表，然后枚举$y$来求解。

在此题，可以先求出$P$的最小原根$g$，根据原根的定义可知$\{g^1,g^2,...,g^{P-1}\}$互不相同，也就是和$\{1,2,...,P-1\}$一一对应，设原题的$x=g^n,B=g^y$（这里求解$y$需要用上面介绍的离散对数），那么要求的是$g^{nA}\equiv g^{y} \pmod P$，等价于$nA\equiv B \pmod {(P-1)}$，用扩展欧几里得算法求出其中一个解（或者判断无解），然后再拓展出其他解即可。

原题链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1038