Josephus for large n (Facebook黑客杯)

Question

上周，我参加了Facebook黑客杯1b轮的比赛。

其中一个问题基本上就是Josephus problem

我以前研究过Josephus问题，作为一个离散的数学问题，所以我基本上理解了如何获得递归：

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添加到结果中将得到原始索引。