AT_kupc2024_f Find x

给定非负整数 $N, M$。 请判断是否存在一个不超过 $10^{18}$ 的正整数 $x$ 满足 $x^x \equiv N \pmod M$，如果存在，求出这样一个 $x$。

输入包含一行，包含两个整数 $N$ 和 $M$。

如果存在一个不超过 $10^{18}$ 的正整数 $x$ 满足 $x^x \equiv N \pmod M$，输出其中一个满足条件的 $x$。如果不存在，输出 $-1$。

## 部分得分 对于 $M$ 为素数的数据点，答对即可获得 1 分。 ## 样例解释 1 $5^5 = 3125 \equiv 3 \pmod 7$ 成立。 ## 样例解释 2 不存在不超过 $10^{18}$ 的正整数 $x$ 满足 $x^x \equiv 2 \pmod 6$。 ## 数据范围 - $0 \leq N < M \leq 10^9$ - 输入的值均为整数。 由 ChatGPT 5 翻译