题目理解

这是 ROI 2018 删除数字 问题的解决方案。题目模拟一个删除过程：每轮删除当前序列中每隔 $k$ 个的数字，求数字 $n$ 在哪一轮被删除。

代码思路解析

1. 模拟删除过程

代码使用循环模拟每一轮删除：

for (long long i = 1; i <= n; i++) {
    if (cp < k) break;          // 剩余数字少于k个，过程结束
    if (cp % k == 0) {          // 检查n是否在本轮被删除
        cout << i;
        return 0;
    }
    cp -= cp / k;               // 计算剩余数字数量
}

2. 关键观察

不需要真正维护整个序列，只需要：

• cp 记录当前轮剩余的数字总数
• 每轮删除 cp/k 个数字
• 当 cp % k == 0 时，最后一个被删除的数字就是本轮最后一个数字

3. 删除规则分析

设当前有 m 个数字，编号为 1..m：

• 删除的数字位置是：k, 2k, 3k, ...
• 如果 m % k == 0，则最后一个数字 m 会被删除
• 否则最后一个数字 m 会保留到下一轮

关键技巧

1. 数量模拟替代序列模拟

不维护具体序列，只维护剩余数字数量

2. 终止条件判断

if (cp < k) break;

剩余数字少于 $k$ 个时过程结束

3. 删除检测

if (cp % k == 0)

当剩余数字数量能被 $k$ 整除时，最后一个数字会被删除

4. 数量更新

cp -= cp / k;

每轮删除 floor(cp/k) 个数字

复杂度分析

时间复杂度：

• 最多循环轮数：$O(\log n)$（每轮数字数量至少减少 $1/k$）
• 每轮操作：$O(1)$
• 总复杂度：$O(\log n)$

空间复杂度：

• $O(1)$，只用了几个变量

正确性验证

样例验证：

$n=13, k=2$

边界情况：

• $n$ 很大时仍能高效计算
• $k=2$ 时是经典约瑟夫问题变种
• 当 $n$ 永远不会被删除时输出 0

总结

这个解法巧妙地将问题转化为数学模拟：

1. 问题简化：发现只需要跟踪剩余数字数量，不需要具体序列
2. 规律发现：当剩余数量能被 $k$ 整除时，最后一个数字被删除
3. 高效模拟：每轮用数学公式更新数量，避免暴力模拟
4. 边界处理：正确处理过程终止和找不到的情况

体现了竞赛中模拟题的优化思路，特别是通过数学观察将 $O(n)$ 模拟优化到 $O(\log n)$ 的技巧。