a683. 01363 - Joseph's Problem - 高中生程式解題系統

內容

約瑟夫很喜歡參加程式比賽。他最喜歡的題目理所當然就是約瑟夫問題。

題目敘述如下:

有n個人編號從0到n-1圍成一圈。從第0個人數到第k個人將會被處決。

在那之後剩下來的人中編號為第k個人會接著被處決，一直到只剩下一個人為止。

這個人變是存活下來的唯一一個人。在這個問題裡將會給定n跟k並求最後生還者一開始的編號。

聰明如你當然知道這個問題的解法。解法相當的短，事實上只需要一個迴圈便可求得。

r := 0;

for i from 1 to n do

r := (r + k) mod i;

return r;

其中 x mod y 表示x除以y後的餘數。

但約瑟夫不是相當的聰明。他懂得這個演算法，卻不懂背後的原理。因此他是實上只記得演算法的一部分，

而誤解了其中的一部分，且告訴他的朋友安卓這著名的問題解法如下:

r := 0;

for i from 1 to n do

r := r + (k mod i);

return r;

安卓當場指證出了約瑟夫的錯誤，但卻也計算出了約瑟夫提供的演算法的錯誤答案結果，作為對照。

給你n和k請找出

^{(k mod i) .}

輸入說明

輸入包含多組測試資料，每組測試資料包含整數n跟k (1n, k10⁹).

輸出說明

對於每組輸入請輸出其對應的和

範例輸入 #1

5 3

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 3.0s , <1M

提示：

標籤:

出處:

UVa 1363 [管理者： snail (蝸牛) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」