題目連結: https://tioj.ck.tp.edu.tw/problems/1004
# 內容
於第一世紀時，猶太人受制於羅馬帝國，一批愛國志士反叛羅馬帝國，最後僅剩下 41 人受困於山洞。這 41 人不想受辱於羅馬帝國，又不想自殺，因此決定圍成一個圓圈，由 1 號開始將 2 號殺掉；3 號將 4 號殺掉，依此類推，即由前一個殺掉下一個，欲將全團 41 人全部殉戰而亡。然而，最後必定會剩下一人。試問哪一號最後得以苟且偷生？如果有 n 個人圍成一圓圈，誰得以殘留餘命呢？
令 f (n) 為最後留下性命的號數，則 f (1)=1。設有 2n 個人，則過了第一圈後所有偶數號的都要被去除，剩下的人為成一圈如下： 1, 3, 5, 2i-1, 2n-3, 2n-1 (接 1)
將其重新編號，則編號為 1 至 n 為成一圈與上述所剩下的人其號碼的對應方式為 i -> 2i-1。
# 思路
想一想。在兩個人的情況下，1 殺死 2。在四個人的情況下，1 殺死 2，3 殺死 4，然後 1 殺死 3。士兵 1 總是重新開始循環。
繞圈一圈之後，您又以 2 的冪返回，士兵 1 再次安全，直到他是剩下的唯一一個。小組每次都將自己減半。
2 次冪的計算是整個問題的關鍵。找出有多少多餘的男人與 2 的最接近冪次比較，您可以得出如何節省效率的方法。那個差值被標記為 “l”，並且該位置為（2 x l）+ 1。
無論開始的時候有多少人，你都要確保你在第 1 個位置，當圓圈縮小到 2 的冪次時，像 16 或 32，你要將 I 重複，因為其他的軍人都被殺了。
約瑟夫是這個關鍵的數字 1，當圓圈開始轉換為 2 的冪次時，他會一直是 1 號，直到其他人都被殺了，這是依據我們所知的情況所計算出來的。
參考自一個神奇網站
# 程式碼
#include <iostream> | |
using namespace std; | |
int main(){ | |
int a,b=1; | |
cin>>a; | |
while(a>=b*2){ | |
b*=2; | |
} | |
cout<<(a-b)*2+1; | |
return 0; | |
} |
