Skip to content

Josephus Problem

一、 什么是约瑟夫环？

定义：

\(n\) 个人（编号 \(1 \sim n\)）围成一圈。从第 1 个人开始报数，报到 \(k\) 的人出局。下一个人从 1 继续报数，直到剩下最后一个人。求这个幸存者的编号。

  • \(n\)：总人数。

  • \(k\)：报数的步长（Kill Step）。

二、 CTF 核心考点 1：特例 \(k=2\)

1. 数学规律

当 \(k=2\) 时，幸存者的编号 \(f(n, 2)\) 满足以下规律：

\[ J(n) = 2 \times (n - 2^{\lfloor \log_2 n \rfloor}) + 1 \]

通俗解释：找到小于等于 \(n\) 的最大 2 的幂（记为 \(2^m\)），将 \(n\) 减去这个幂，剩下的数乘 2 再加 1。

2. 二进制“魔法”（循环左移）

这是 CTF 选手必须秒懂的技巧：

\(k=2\) 的约瑟夫环结果，等于将 \(n\) 的二进制表示循环左移一位（Rotate Left）。

  • 操作：把二进制最左边（最高位）的 1 移到最右边。

  • 例子（回忆之前的题目）：

    • \(n = 100\) (二进制 1100100)

    • 最高位 1 移到末尾 \(\to\) 1001001

    • 结果 \(= 73\)。

3. 代码实现

def josephus_k2(n):
    # 方法1：数学公式
    # highest_bit = 1 << (n.bit_length() - 1)
    # return (n - highest_bit) * 2 + 1

    # 方法2：字符串操作（更直观）
    bin_str = bin(n)[2:]
    rotated = bin_str[1:] + bin_str[0]
    return int(rotated, 2)

三、 CTF 核心考点 2：通用公式 (\(O(n)\) 复杂度)

当 \(k \neq 2\) 且 \(n\) 在 \(10^7\) 以内时，需要使用线性递推公式。这通常出现在 PPC（编程类） 题目中。

1. 0-based 索引公式（从 0 开始编号）

为了方便取模，通常假设人是 \(0 \sim n-1\)。

\[ f(n, k) = (f(n-1, k) + k) \% n \]
  • Base Case: \(f(1, k) = 0\) （只有 1 个人时，幸存者索引是 0）。

2. 1-based 索引转换

如果题目要求从 1 开始编号（CTF 常见情况）：

\[ Result = f(n, k) + 1 \]

3. 代码实现

def josephus_linear(n, k):
    res = 0  # 对应 f(1, k) = 0
    for i in range(2, n + 1):
        res = (res + k) % i
    return res + 1  # 转化为 1-based

四、 CTF 核心考点 3：大数优化 (\(n\) 极大， \(k\) 较小)

如果题目给出 \(n = 10^{18}\) 这种天文数字，但 \(k\) 比较小（例如 \(k=3\)），上面的 \(O(n)\) 算法会超时。需要 跳跃优化（加速递推）。

原理：

不需要每次只杀一个人。当 \(n \gg k\) 时，在这一圈里可以连续删掉 \(\lfloor n/k \rfloor\) 个人，而不用担心索引越界。可以直接跳过这部分计算。

代码模板：

def josephus_large_n(n, k):
    if k == 1: return n - 1
    res = 0
    i = 1
    while i <= n:
        # 当前 res 在当前 i 个人中的位置
        # 我们想跳跃步数 step
        # 下一个必须重新计算的点是当 (res + step * k) >= 当前总人数
        if res + k >= i:
            # 无法跳跃，退化为单步
            res = (res + k) % i
            i += 1
            continue

        # 计算可以跳多少步
        # 这种情况下，人数从 i 增加到 i + step
        # 使得 res 依然没有这就溢出
        step = (i - res - 1) // (k - 1)
        if i + step > n: # 不能超过目标 n
            step = n - i

        if step == 0: # 避免死循环，强行单步
             res = (res + k) % i
             i += 1
        else:
            i += step
            res = (res + step * k)

    return res + 1

(注：这种大数情况多见于 ACM 或高级 Crypto 构造题，Reverse 中较少见)

五、 逆向工程中的“特征识别”

  1. 链表结构：

    如果你看到程序在堆（Heap）上构建了一个循环链表（next 指针指向 head），并且有一个循环逻辑不断执行 free 或 delete 操作，且每次跳过固定的次数，这就是模拟法的约瑟夫环。

  2. 数组取模：

    如果看到一个数组，并且索引操作频繁出现 index = (index + k) % current_size，且伴随着元素的移除（memmove 覆盖或标记为 -1），这是数组模拟法。

  3. 位运算特征 (\(k=2\))：

    在没有明显循环结构的情况下，出现了 HighestBit 的提取、SHL（左移）、OR（或运算）以及减法，且输入输出符合 \(f(n) \approx 2n\)，这极大概率是 \(k=2\) 的优化实现。

六、 总结表

场景 特征 解决方法
PPC/Algorithm \(n\) 较小 (\(<10^7\)) \(O(n)\) 线性递推公式
PPC/Crypto \(n\) 极大 (\(10^{18}\)), \(k\) 较小 对数级跳跃递推算法
Reverse/Crypto \(k=2\) 二进制循环左移 (最重要)
Reverse 链表/数组模拟 识别出 delete 逻辑，写脚本模拟