CF172B Pseudorandom Sequence Period

Polycarpus 最近对伪随机数序列产生了兴趣。他了解到，许多编程语言通过相似的方式生成这样的序列： $$ r_{i} = (a \cdot r_{i-1} + b) \bmod m $$ （其中 $i \geq 1$）。这里 $a$、$b$、$m$ 是常数，由该伪随机数生成器的实现所确定，$r_0$ 是所谓的随机种子 randseed（可以通过如 RandSeed(r) 或 srand(n) 这样的函数设置），而 $\bmod$ 符号表示取余运算。 例如，如果 $a = 2, b = 6, m = 12, r_0 = 11$，那么生成的序列为：$4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10,...$。 Polycarpus 发现任何这样的序列迟早都会形成一个循环，但循环部分可能不会一开始就出现，因此存在一个前置部分（preperiod）和周期部分。例如上述例子中，前置部分的长度为 1，周期为 2。 你的任务是给定 $a,b,m$ 和 $r_0$ 的值，求出该序列的周期长度。形式化地说，你需要找到最小的正整数 $t$，使得存在某个正整数 $k$，对于所有 $i \geq k$ 都有 $r_i = r_{i+t}$。

输入仅一行，包含四个整数 $a$、$b$、$m$ 和 $r_0$（$1 \leq m \leq 10^5, 0 \leq a, b \leq 1000, 0 \leq r_0 < m$），用空格隔开。

输出一个整数，表示该序列的周期长度。

第一个样例已在上文中描述。 第二个样例得到的序列（从第一个元素开始）为：$0,3,4,1,0,3,4,1,0,...$。 第三个样例得到的序列（从第一个元素开始）为：$33,24,78,78,78,78,...$。 由 ChatGPT 5 翻译