解题思路
小蓝定义的数列生成规则为:从 x=1 开始,反复将 x 更新为 (x×p)modq。由于 x 的取值只有 0 到 q−1 这 q 种可能,整个序列在更新足够多次后必然会进入循环。题目要求“无限次操作中一共会产生多少个不同的 x 值”,这等价于从初始值 1 开始,沿着更新规则一直走,直到第一次遇到之前出现过的值为止,其间访问过的不同值的个数。
具体模拟过程如下:
- 维护一个布尔数组
visited(或等效的标记结构),用于记录某个值是否已经被访问过。
- 将初始值设为 x=1。
- 重复以下步骤,直到当前 x 已经出现在
visited 中: