約瑟夫環

題目描述

nn?個人的編號是 1 ~?nn，如果他們依編號按順時針排成一個圓圈，從編號是 1 的人開始順時針報數。

（報數是從 1 報起）當報到?kk?的時候，這個人就退出游戲圈。下一個人重新從 1 開始報數。

求最后剩下的人的編號。這就是著名的約瑟夫環問題。

本題目就是已知?n，kn，k?的情況下，求最后剩下的人的編號。

輸入描述

輸入是一行，2 個空格分開的整數?n,k?(0<n,k<107)n,k?(0<n,k<107)。

輸出描述

要求輸出一個整數，表示最后剩下的人的編號。

輸入輸出樣例

示例

輸入

10 3

輸出

4

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

總通過次數: 2020??|??總提交次數: 2706??|??通過率: 74.6%

難度: 中等???標簽: 2018, 規律, 思維, 國賽, 遞歸

方法思路

為了解決約瑟夫環問題，我們可以使用遞推公式來避免模擬過程的高時間復雜度（O(n*k)）。遞推公式基于以下思路：

1. 問題轉化：將人的編號從0到n-1（最后結果再加1轉回1到n），這樣便于數學處理。

2. 遞推關系：設f(n, k)表示n個人報數到k時最后剩下的人的編號（0到n-1）。當n=1時，f(1, k) = 0。對于n>1，有遞推公式：f(n, k) = (f(n-1, k) + k) % n。

3. 遞推過程：從i=2開始到n，依次計算f(i, k) = (f(i-1, k) + k) % i。這樣避免了遞歸或模擬的高開銷。

4. 結果轉換：最終結果f(n, k) + 1即為原始編號（1到n）

   #include <iostream>
   using namespace std;int main() {int n, k;cin >> n >> k;int ans = 0; // 初始化n=1時的結果（編號0）for (int i = 2; i <= n; i++) {ans = (ans + k) % i; // 遞推公式}cout << ans + 1 << endl; // 將編號轉回1~nreturn 0;
   }

   代碼解釋

5. 輸入處理：讀取兩個整數n（總人數）和k（報數到k出圈）。

6. 初始化：ans初始化為0，表示當n=1時剩下的人的編號（0）。

7. 遞推計算：循環從2到n，每次更新ans為(ans + k) % i：

   • ans：上一輪（i-1人）的存活編號。

   • (ans + k) % i：當前i人時，存活編號的遞推計算。

8. 結果轉換：最終ans是0到n-1編號下的結果，加1后轉換為1到n的編號輸出。