Josephus for large n（Facebook Hacker Cup）

Question

先週、私はFacebookのハッカーカップのラウンド1bに参加しました。

問題の一つは、基本的にJosephus problem

私は離散数学の問題として前にヨセフスの問題を研究してきたので、私は基本的に再発を取得する方法を理解しました：

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

しかし、のdidnことnの最大値は10^12だったので、Facebook Hacker Cupで作業していません。 kのmak値は10^4であった。

ウィキペディアは、kが小さく、nが大きい場合のアプローチについて言及しています。基本的に、1つのラウンドから人を取り除き、番号を付け直します。 しかし、これはあまり説明されていないので、なぜ番号付けが機能するのかわかりません。

解決策のサンプルソースコードを見ましたが、私はまだその最終部分を理解していません。

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またはトップコードフォーラムに関する情報は見つかりませんでした）

Answer 1

右、私はそれをクラックしたと思います。

、の反復が一緒に行くのn = 10方法を見てみましょうK = 3：最初の1に第2の反復マップのどの要素を守っ

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を減算して結果を修正しています。 2行目の数字は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）であることが判明5%3により補正0を返す-2。これは、2番目の行の結果が最後のグループにある場合にのみ発生します。この場合、結果にnを追加すると元のインデックスが返されます。