n個人編號為0…n-1圍成一個圈,從0開始報數,每經過k個人那個人就退出這個圈不再報數,問最后留下來的人的編號.

樸素的做法當然是模擬,但是n,k的值一旦變得比較大的時候就難以解決問題.

我們考慮歸納的解決問題
當只有一個人的時候答案顯然為0,
假設我們已知n-1個人的時候答案為ans[n-1],那么當人數為n時
顯然的,我們首先得選一個人出去,這個人是(k-1)%n,然后我們從下一個起點(k%n)開始算起,我們不難發現問題變成了n-1個人的問題,因此ans[n]=(ans[n-1]+k)%n

可是這樣當n比較大的時候我們還是難以很快的解決問題.當n比較大的時候,前n/k次我們都是很容易確定的,因此我們直接考慮$Josephus(n?n/k,k)$,直到n-n/k小于k,這樣就能很快將復雜度變成O(k)級別的.根據剛才的想法,$Josephus(n,k)=Josephus(n?n/k,k)+n/k?k$就可以了嗎?問題并不是這么簡單.
我們看一個例子:
當n=10,k=4的時候我們選擇兩次以后的序列為
0 1 2 * 4 5 6 * 8 9
因此我們應該考慮n=8的情況
2 3 4 * 5 6 7 * 0 1
假設n=8時最后選出來的人為5,按照上面的式子原答案為(5+8)%10=3,但是正確的答案卻應該是4,問題出在哪里呢?
原來我們選過以后的數列不是連續的了,必須考慮已經選過的沒法再次選.我們觀察,對于n=8時,越過n%k后每4-1個數出現一個已經選擇后的情況,需要加1

所以我們分類討論:
設s’=$Josephus(n?n/k,k)$
當s’<n%k時,s=s’+n/k*k;
當s’>=n%k時,s=s’-n%k+(s’-n%k)/(k-1)

根據上面的討論我們得到解決問題的算法:

int Josephus(int n,int k)
{if(n==1) return 0;int ret;if(n<k){ret=0;for(int i=2;i<=n;i++){ret=(ret+k)%i;}return ret;}ret=Josephus(n-n/k,k);if(ret<n%k){ret+=n/k*k;}else{ret-=n%k;ret+=ret/(k-1);}return ret;
}