寻找循环的问题

1. Introduction

假设你有一个函数 f: S → S 和任何初始值 x₀ ∈ S
(在这个可视化中，我们限制为 f(x) = (A*x^2 + B*x + C) % M 和 x₀ % M，因此函数 f 的定义域和值域 ∈ [0..M-1])。

迭代函数值的序列：
{x₀, x₁ = f(x₀), x₂ = f(x₁), ..., x_i = f(x_i-1), ...}
必须最终使用两次相同的值（循环），即 a ≠ b 使得 x_a = x_b。
之后，序列必须通过重复从 x_a 到 x_b-1 的值的循环来继续。

设 mu (μ) 是最小的索引，设 lambda (λ)（循环长度）是最小的正整数，使得 x_μ = x_μ+λ。

寻找循环问题：给定 f 和 x₀，找到这样的 μ 和 λ。

2. 自定义输入

您可以在此处定义自定义函数 f(x) = (A*x² + B*x + C) % M。

1. 随机：函数将为 f(x) = (x² - 1) % M，只有 M 和 x₀ 是随机生成的。
2. 自定义：您可以指定 f(x) 的系数 A、B、C（范围从 -999 到 999），模数值 M（范围从 10 到 1000）和初始值 x₀（范围从 0 到 M-1）。

您还可以设置自定义 x₀，必须 ∈ [0..M-1]。

3. Floyd's 乌龟 - 野兔算法

Floyd's Tortoise-Hare Cycle-Finding is one algorithm that can solve this problem efficiently in both time and space complexities.

It just requires O(μ+λ) time and O(1) space to do the job.

3-1. 可视化

This is the visualization of Floyd's Tortoise-Hare Cycle-Finding algorithm.

The shape of rho (ρ) of the sequence of iterated function values defined by f(x) and x₀ nicely visualizes μ and λ.

VisuAlgo uses green vertices to represent the tortoise (t) and orange vertices to represent the hare (h).

3-2. 寻找 kλ (λ的倍数)

我们从 x₀ 开始。

当 乌龟的指针 != 兔子的指针 时，我们通过调用 f(乌龟)/f(f(兔子)) 将 乌龟/兔子 向前推进一步/两步到他们的下一个值。

3-3. 寻找 μ (循环的开始)

我们将 hare 重置回 x₀，并保持 tortoise 在其当前位置。

然后，我们将两个指针迭代地向前移动一步，因为这样可以保持 tortoise 和 hare 的间隔为 kλ。

两个指针第一次相等时，就告诉我们 μ 的值。

3-4. 寻找 λ (循环的长度)

再次，我们让乌龟保持在其当前位置，并将兔子设置在它旁边。

然后，我们通过一步一步地将兔子移动到下一个值。

两个指针第一次相等告诉我们λ的值。

4. 试试这个动画！

5. 实现

You are allowed to use/modify our implementation code for Floyd Cycle-Finding Algorithm:
UVa00350.cpp
UVa00350.java
UVa00350.py
UVa00350.ml