← 返回题目列表

Codeforces · 1027/G

G. 校园里的X鼠

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

校园有 $$$m$$$ 个房间,编号从 $$$0$$$ 到 $$$m - 1$$$。 $$$x$$$ 老鼠也住在校园里。 $$$x$$$-鼠标不仅仅是一只鼠标:每秒 $$$x$$$-鼠标从房间 $$$i$$$ 移动到房间 $$$i \cdot x \mod{m}$$$ (事实上,它从一个房间传送到另一个房间,因为它不访问任何中间房间)。 $$$x$$$-鼠标的起始位置未知。

你有责任在校园里捕捉$$$x$$$-老鼠,所以你正在猜测你需要放置的最少可能数量的陷阱(一个房间一个陷阱)。您确信如果$$$x$$$-鼠标进入被困的房间,它会立即被抓住。

您所做的唯一观察是 $$$\text{GCD} (x, m) = 1$$$。

输入

唯一一行包含两个整数 $$$m$$$ 和 $$$x$$$ ($$$2 \le m \le 10^{14}$$$, $$$1 \le x < m$$$, $$$\text{GCD} (x, m) = 1$$$) — 房间数量和 $$$x$$$-鼠标的参数。

输出

打印唯一的整数 — 捕获 $$$x$$$ 鼠标所需安装的最小陷阱数。

示例

输入 #1

4 3

输出 #1

3

输入 #2

5 2

输出 #2

2

注意

在第一个示例中,您可以将陷阱放置在房间 $$$0$$$、$$$2$$$、$$$3$$$ 中。如果 $$$x$$$ 鼠标在其中一个房间中启动,它将立即被捕获。如果 $$$x$$$-鼠标从 $$$1$$$-st 房间开始,那么它将移动到 $$$3$$$ 房间,并在那里被抓住。

在第二个示例中,您可以在房间 $$$0$$$ 中放置一个陷阱,并在任何其他房间中放置一个陷阱,因为 $$$x$$$ - 鼠标将访问所有房间 $$$1..m-1$$$(如果它从这些房间中的任何一个开始)。