解题思路

这道题是 约瑟夫问题（Josephus Problem） 的一个变种，要求找到最小的 $m$，使得在 $n$ 个城市的环形排列中，按照 每隔 $m-1$ 个城市删除一个城市 的规则，$2$ 号城市（乌尔姆）最后被删除。

关键点

1. 约瑟夫问题背景：

   • 经典约瑟夫问题：$n$ 个人围成一圈，从某个起点开始，每数到 $k$ 的人出局，求最后剩下的人的位置。
   • 本题的变种：
     • 固定起点为 $1$（第一个删除的是 $1$）。
     • 目标是让 $2$ 号城市最后被删除。
     • 需要找到最小的 $m$（步长），使得在 $n-1$ 次删除后，$2$ 号城市仍然存在。

2. 模拟删除过程：

   • 对于每个可能的 $m$（从 $1$ 开始递增），模拟删除过程，直到 $2$ 号城市成为最后一个未被删除的城市。
   • 由于 $n$ 的范围较小（$n < 150$），可以采用 暴力枚举 的方法，逐个尝试 $m$ 并验证是否满足条件。

3. 优化方法：

   • 如果直接暴力模拟，时间复杂度为 $O(n \times m)$，但由于 $n$ 较小，仍然可行。
   • 可以进一步优化，比如 数学推导 或 递推公式，但本题数据规模下暴力模拟已经足够。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 检查当前 m 是否满足条件：2 号城市最后剩下
bool isValid(int n, int m) {
    vector<bool> removed(n + 1, false); // 1-based 索引
    removed[1] = true; // 初始删除 1 号城市
    int current = 1; // 当前指针（初始在 1 号城市）
    int remaining = n - 1; // 剩余城市数量（初始已经删除了 1 号）

    while (remaining > 1) {
        int count = 0;
        // 找到第 m 个未被删除的城市
        while (count < m) {
            current = (current % n) + 1; // 循环遍历
            if (!removed[current]) {
                count++;
            }
        }
        // 如果删除的是 2 号城市，直接返回 false
        if (current == 2) {
            return false;
        }
        removed[current] = true; // 标记为已删除
        remaining--;
    }
    // 最后剩下的必须是 2 号城市
    return true;
}

int findMinM(int n) {
    for (int m = 1; ; m++) {
        if (isValid(n, m)) {
            return m;
        }
    }
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        cout << findMinM(n) << endl;
    }
    return 0;
}