#P5348. 随机数生成器

    ID: 4361 传统题 1000ms 256MiB 尝试: 16 已通过: 4 难度: 8 上传者: 标签>CF2400提高+/省选-中国剩余定理群欧拉函数欧几里得算法Miller–RabinPollard–Rho快速幂快速乘防溢出

随机数生成器

Description

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

Format

Input

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

Output

输出一个数表示答案。

Samples

10 2
4