小编Edw*_*nai的帖子

上周我参加了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论坛的任何信息)