问题分析

我们有 n 只雄鸟和 m 只雌鸟围成一圈，按照特定规则轮流唱歌并飞走。需要找出第 k 只飞走的鸟的编号。

核心难点：n 和 m 最大可达 10⁹，k 最大可达 n+m，直接模拟会超时。

关键观察

1. 状态表示

整个过程可以由三个变量完全描述：

• 当前剩余鸟的总数 total
• 当前起始位置 start（从0开始编号便于计算）
• 当前歌曲类型 song_type（0表示「我的小鸽子」，1表示「我爱你小鸽子」）

2. 飞走位置计算

• 唱「我的小鸽子」时，飞走位置 = (start + a - 1) mod total
• 唱「我爱你小鸽子」时，飞走位置 = (start + b - 1) mod total

3. 状态转移

• 如果飞走的是雄鸟（编号 ≤ n），下一首唱「我的小鸽子」
• 如果飞走的是雌鸟（编号 > n），下一首唱「我爱你小鸽子」
• 新的起始位置是飞走位置的下一个位置
• 剩余鸟数减1

优化策略

基础优化

直接按照上述状态转移模拟，但使用数学计算代替物理移动。这种方法对于 k ≤ 3×10⁶ 的数据足够高效。

进阶优化：循环节检测

由于状态空间有限（song_type 只有2种取值，start 的范围受 total 限制），状态序列必然会出现循环。我们可以：

1. 记录每个状态（start, song_type, total）第一次出现时的迭代次数
2. 当状态重复出现时，检测到循环节
3. 计算循环长度，直接跳过完整的循环周期

这样可以将时间复杂度从 O(k) 优化到 O(状态空间大小)。

算法流程

1. 初始化 total = n + m, start = 0, song_type = 0
2. 对于 i 从 1 到 k：
   • 根据当前歌曲类型计算飞走位置
   • 如果 i = k，输出结果并结束
   • 根据飞走鸟的性别更新 song_type
   • 更新 start 和 total
   • 检查状态是否形成循环，如发现则跳过完整循环

复杂度分析

• 时间复杂度：最坏 O(k)，但循环节检测使其在实际中远优于线性
• 空间复杂度：O(状态数量)，由于状态空间有限，实际占用很小

总结

本题的关键在于将物理模拟转化为状态转移，并通过数学计算和循环节检测来优化性能。这种「数学化模拟」的思想在处理大规模数据时非常有效。