N次剩余

51nod 1038
题意:
求\(X^A \equiv B (\% P)\)所有小于p的X。

1.先求出\(P\)的原根\(g\)。
2.设\(x=g^y\),\(B=g^t\)。那么原式化为:\(g^{yA} \equiv g^t(\% P)\)。根据费马小定理化为\(yA\equiv t(\% P-1)\)。
3.\(B\equiv g^t(\% P)\)通过BSGS求出\(t\)。
4.通过扩展欧几里得求线性同余方程最简解,然后扩展。

Leave a Reply

Your email address will not be published. Required fields are marked *