题目描述

校园里有 $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 \lt m$ , $\text{GCD} (x, m) = 1$ ) 。

输出格式

仅输出一个整数，表示最少布置的老鼠夹数。

by @_I°Fear