之前有人问过这个问题，但是没有一个得到明确的回答，我尝试编译我在这里找到的所有信息。如有必要，请随意合并/移动到另一个 stackexchange 站点。
以下是我发现的与此相关的问题：
该问题最初是作为 Interviewstreet Code Sprint 发布的，但现在它被列为实践问题。它也被移植到 SPOJ。
这是问题陈述：
这是洗牌 N 张牌的算法：
1) 将牌分成 K 个相等的牌堆。
2）最底的N/K张牌同顺序属于1堆（所以初始堆的底牌就是1堆的底）。
3）从底部开始的下 N / K 张牌属于第 2 堆，依此类推。
4) 现在洗好的牌堆的顶牌是1堆的顶牌。下一张牌是2堆顶的牌，...，洗好的牌堆的第K张牌是K堆顶>牌。那么第（K + 1）张牌是现在在第 1 堆顶部的牌，第（K + 2）张是现在在第 2 堆顶部的牌，依此类推。
例如，如果 N = 6 且 K = 3，则一副牌“ABCDEF”（从上到下）洗牌一次时的顺序将变为“ECAFDB”。
给定 N 和 K，在堆恢复到其原始顺序之后需要的最少洗牌次数是多少？
输入：第一行包含测试用例 T 的数量。接下来的 T 行包含两个整数，每个整数 N 和 K。
输出：输出 T 行，每个测试用例包含所需的最小洗牌次数。如果套牌永远不会恢复到原来的顺序，则输出 -1。
约束：
- K 将是 N 的一个因子。
- T <= 10000
- 2 <= K <= N <= 10^9
剧透警报 - 如果您想自己解决，请不要阅读下文。
问题可以翻译为：
找出需要执行 K 路（完美）洗牌的次数，以将一副 N 牌恢复到其初始顺序。
我采取了两种方法来解决这个问题。想到的第一个方法是：
- 找到一个公式，给定初始顺序中的位置将生成卡片的下一个位置
- 使用公式确定从第一堆（大小为 n / k）中的每张牌返回其初始位置所需的洗牌次数
- 返回之前确定的随机数的最小公倍数
该解决方案的复杂度为 O(n / k + max_number_of_suhffles)。这是实际的实现。这样做的问题是它超过了最大时间，所以我开始寻找一个公式，可以让我在接近恒定的时间内得到这个数字。
我在这里可以优化的最多（例如，使用一些映射来缓存相同排列循环中的计算值等）是使其通过 interviewstreet 上的 3/10 测试。
我找到了这个实现，它假设返回初始状态所需的洗牌次数是K 相对于 N + 1的乘法顺序。来自 wiki：
As a consequence of Lagrange's theorem, ordn(a) always divides φ(n).
φ(n) 是欧拉函数， ordn 是群阶——我们正在寻找的。我发现这篇论文使用 φ 来计算 shuffle 的数量，但它只适用于 2-way in-shuffle，而不是 k-way。
以下是此实施的步骤：
- 预先计算出 < 100 000 的素数列表
φ(N+1)从它的主要因素计算。φ(N + 1)通过以所有可能的方式组合其主要因素来确定所有的因素。- 依次尝试每个因素，得到最小的一个，
x，验证k ^ x % N + 1 = 1
这个实现也发布在 GitHub 上。
这运行得非常快，但自动评分器在 SPOJ 和 Interviewstreet 上的 10 次测试中有 9 次给了我一个“错误答案”分类。
我尝试比较两个实现的输出，但是对于我输入的测试用例（已知结果和随机），这两个实现总是输出相同的东西。这很奇怪，因为我很确定第一个算法是正确的，我认为第二个算法也应该是正确的。
“错误答案”分类可能来自代码中的运行时错误，但没有任何可能的原因跳出来。
我没有考虑到没有数字洗牌可以将牌组恢复到初始状态的情况——我的理解是这是不可能的。有限数量的完美洗牌最终将恢复初始排序，即使洗牌的数量可能非常高。
如果您花时间阅读本文，谢谢。:) 我很好奇这个问题，我想解决它。