305412: CF1027G. X-mouse in the Campus
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
X-mouse in the Campus
题意翻译
校园里有 $m$ 个房间,编号 $ 0 $ 到 $ m - 1 $。还有一只 $x$-老鼠住在校园里。$x$-老鼠不仅仅是一只老鼠。每秒,$x$-老鼠从 $i$ 号房间跑到 $i \cdot x \bmod 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 $)。 **【输出格式】** 仅输出一个整数,表示最少布置的老鼠夹数。题目描述
The campus has $ m $ rooms numbered from $ 0 $ to $ m - 1 $ . Also the $ x $ -mouse lives in the campus. The $ x $ -mouse is not just a mouse: each second $ x $ -mouse moves from room $ i $ to the room $ i \cdot x \mod{m} $ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $ x $ -mouse is unknown. You are responsible to catch the $ x $ -mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $ x $ -mouse enters a trapped room, it immediately gets caught. And the only observation you made is $ \text{GCD} (x, m) = 1 $ .输入输出格式
输入格式
The only line contains two integers $ m $ and $ x $ ( $ 2 \le m \le 10^{14} $ , $ 1 \le x < m $ , $ \text{GCD} (x, m) = 1 $ ) — the number of rooms and the parameter of $ x $ -mouse.
输出格式
Print the only integer — minimum number of traps you need to install to catch the $ x $ -mouse.
输入输出样例
输入样例 #1
4 3
输出样例 #1
3
输入样例 #2
5 2
输出样例 #2
2