← 返回题目列表

Codeforces · 172/B

B. 伪随机序列周期

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

Polycarpus 最近对伪随机数序列产生了兴趣。他了解到许多编程语言都以类似的方式生成这样的序列:$$r_{i} = (a \cdot r_{i-1} + b) \mod m$$(对于 i ≥ 1)。这里 a、b、m 是常数,对于伪随机数生成器的给定实现是固定的,r0 是所谓的 randseed(该值可以使用 RandSeed(r) 或 srand(n) 等函数从程序中设置),$$\bmod$$ 表示取除法余数的操作。

例如,如果 a = 2、b = 6、m = 12、r0 = 11,则生成的序列将为:4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....

波利卡普斯意识到任何这样的序列迟早都会形成一个循环,但这个循环可能不是在一开始就发生的,因此存在前期和后期。上面的示例显示前期等于 1,期间等于 2。

您的任务是找到由给定的 a、b、m 和 r0 值定义的序列的周期。形式上,你必须找到这样的最小正整数 t,其中存在这样的正整数 k,对于任何 i ≥ k:ri = ri + t。

输入

输入的单行包含四个整数 a、b、m 和 r0 (1 ≤ m ≤ 105, 0 ≤ a, b ≤ 1000, 0 ≤ r0 < m),用单个空格分隔。

输出

打印一个整数——序列的周期。

示例

输入 #1

2 6 12 11

输出 #1

2

输入 #2

2 3 5 1

输出 #2

4

输入 #3

3 6 81 9

输出 #3

1

注意

第一个示例如上所述。

在第二个示例中,序列为(从第一个元素开始):0, 3, 4, 1, 0, 3, 4, 1, 0, ...

在第三个示例中,序列为(从第一个元素开始):33, 24, 78, 78, 78, 78, ...