F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5348. -- 随机数生成器

5348: 随机数生成器

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 9  Solved: 0
[Submit][Status][Discuss]

Description

你有一个随机数生成器,给定一个0<=x<=n-1的整数作为随机种子,这个随机数生成器会每次输出x 并将xk mod n 
作为新的x。你很快发现这个随机数生成器很渣。为了证明它很渣,你想要求出有多少个随机种子,使得这个随机
数生成器会输出初始种子无穷多次。

Input

输入一行两个正整数n和k。
n <=10^18,k<=10^18。

Output

输出一个数表示答案。

Sample Input

10 2

Sample Output

4

HINT

Source

[Submit][Status][Discuss]

HOME Back