为何Juggling算法中循环起始位置始终连续？

这绝对不是小例子的巧合，而是由数论中的最大公约数（gcd）性质保证的必然结果，下面给你拆解清楚：

• 首先明确定义：设数组长度为n，左移偏移量为d，计算g = gcd(n, d)。我们可以把n和d分解为：n = g * a，d = g * b，这里的a和b满足gcd(a, b) = 1（因为已经提取了最大公约数）。

• 接下来看Juggling算法里的循环结构：每个循环包含的元素是索引i, i+d, i+2d, ..., i+kd (mod n)。把这些索引代入分解后的式子：
  i + k*d = i + k*g*b，模n=g*a后可以写成g*((i//g + k*b) mod a) + (i % g)（如果i < g，那i//g=0，i%g=i）。

• 这里的关键结论：每个循环里的所有索引，除以g的余数都相同。比如i=0时，所有循环内的索引除以g余数都是0；i=1时余数都是1，以此类推。

• 而除以g的余数只有0,1,...,g-1这g种可能，每种余数对应一个独立的循环。所以只要从0到g-1每个余数选一个起始点，就能覆盖所有g个循环，不需要选分散的索引——因为分散的索引必然属于这g个余数类中的某一个，只会重复处理已经覆盖的循环。

举两个你提到的例子验证：

1. n=6, d=2：g=2，a=3，b=1（gcd(3,1)=1）

   • 余数0的循环：0 → 0+2=2 → 2+2=4 → 4+2=6≡0
   • 余数1的循环：1 →1+2=3 →3+2=5 →5+2=7≡1
     刚好对应起始索引0和1，覆盖所有元素。

2. n=6, d=3：g=3，a=2，b=1（gcd(2,1)=1）

   • 余数0的循环：0 →0+3=3 →3+3=6≡0
   • 余数1的循环：1 →1+3=4 →4+3=7≡1
   • 余数2的循环：2 →2+3=5 →5+3=8≡2
     起始索引0、1、2正好对应三个余数类，覆盖全部循环。

简单说，Juggling算法的循环划分本质是按索引对g的余数分类，而0到g-1刚好是所有可能的余数，所以必然是这些连续索引作为循环起始点。

内容的提问来源于stack exchange，提问作者CN.hitori