← 返回题目列表

AtCoder · kupc2024_f

F. 查找 x

中文机器翻译题面 查看原题

配点 : 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 不存在。