Josephus for large n(Facebook黑客杯)

Question

上周我参加了Facebook Hacker杯的第1b轮比赛.

其中一个问题基本上是约瑟夫斯问题

我之前研究过约瑟夫斯问题是一个离散的数学问题,所以我基本上理解如何得到重现:

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

但这在Facebook黑客杯中没有用,因为n的最大值是10 ^ 12.k的mak值为10 ^ 4.

当k很小而n很大时,维基百科提到了一种方法.基本上从一轮中删除人,然后重新编号.但它没有多少描述,我不明白为什么重编号工作.

我查看了解决方案的示例工作源代码,但我仍然不明白最后一部分.

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

我真正不理解的部分是从res-=n%k(以及之后的行)开始.你如何得出那是调整结果的方法？

有人能否证明这是如何衍生出来的？或者是一个派生它的链接？(我没有找到关于UVA或topcoder论坛的任何信息)

Answer 1

好吧，我想我已经破解了。

让我们看看 n=10、k=3 时的迭代情况：

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

观察第二次迭代的元素如何映射到第一次迭代：它们被 转置n%k，因为圆圈环绕。这就是为什么我们通过减去 来校正结果10%3。第二行中的数字以 组出现k-1，因此通过 进行校正res/(k-1)。

另一种情况在迭代过程中受到进一步影响

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

现在 j(4,3) 返回 0，经 修正后结果5%3为 -2。仅当第二行的结果位于最后一组时才会发生这种情况，在这种情况下，添加n到结果中将为我们提供原始索引。