奇奇怪怪的約瑟夫問題？

約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數，第M個將被殺掉，最後剩下一個，其餘人都將被殺掉。例如N=6，M=5，被殺掉的順序是：5，4，6，2，3，1。

當n和m等於什麼（關係或數值）時，讓後二分之n的人先出列

求可行解和最小解

文化課前一天熬夜沒事情干答一下這個題吧。

大概意思就是這個題吧。=@@problem.Title 問題 - 51Nod

這個題應該是沒有什麼規律或者靠譜的多項式做法的，最起碼我沒有找到。

為了方便只說最小解。

顯然我們可以在O(n)時間內判斷一個答案是否合法。

同時我們會發現求M的問題等價於找一個數滿足若干個同餘方程的解。

但是並不能直接用CRT搞因為需要被滿足的同餘方程是可選擇的並不唯一。

那麼一個簡單粗暴的想法就是枚舉每一種情況來CRT求出這種情況的合法解，最後選擇最小的。

但是當N過大的時候情況會達到 的規模。

不妨採用MEET IN THE MIDDLE的思想，只枚舉其中幾個同餘方程的情況，因為同餘方程的性質，對於枚舉的某種情況，合法的答案一定是 這樣的形式。

那麼就對於每種我們枚舉的情況，從小到大枚舉那個 ，動態維護一個堆維護當前每個狀態 的值，然後再在 時間內驗證沒有枚舉的同餘方程，假如不合法的話就驗證下一個稍微更大一些的直到找到一個合法解。

這樣就可以跑出大約 的最小的M啦