配点 : 100 点
問題文
非負整数 N, M 。
10^{18} 的正整数 x 判断是否存在满足 x^x \equiv N \pmod M 的东西,如果存在, x 在 1 请找到一个。
制約
- 0 \leq N < M \leq 10^9
- 所有输入值均为整数
部分点
如果正确答案是满足以下约束的数据集, 1 点。
- M 是素数 如果存在满足
入力
输入是按以下格式从标准输入给出的。
N M
出力
10^{18} 的正整数 x 判断是否存在满足 x^x \equiv N \pmod M 的东西,那么这样 x 的值 1 输出一。像那样 当 x 不存在时,-1 。
入力例 1
3 7
出力例 1
5
5^5 = 3125 \equiv 3 \pmod 7 。
入力例 2
2 6
出力例 2
-1
x^x \equiv 2 \pmod 6 纳鲁 10^{18} 的正整数 x 不存在。