题目链接：P1150 Peter 的烟 - 洛谷

一、题目复述

Peter 有 n 根烟，每抽完 k 根烟的烟蒂可以换一根新烟。Peter 可以无限次地用烟蒂换烟。问 Peter 一共能抽多少根烟。

数据范围：1 ≤ n, k ≤ 10⁶。

样例：n = 3, k = 2 → 输出 5（抽完 3 根得 3 个烟蒂 → 换 1 根 → 抽完又得 1 个烟蒂，共 5 根）。

二、直觉：循环模拟

最直观的写法是「不断用烟蒂换烟，直到不够为止」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    long long total = n;        // 已经抽的烟数（也是手里烟蒂数）
    long long butts = n;        // 当前手里的烟蒂数

    while (butts >= k) {
        long long newCig = butts / k;    // 这一轮换出的新烟
        total += newCig;                  // 多抽了 newCig 根
        butts = butts % k + newCig;       // 换剩下的旧烟蒂 + 新烟的烟蒂
    }

    cout << total;
    return 0;
}

while 的语义很清楚：每轮尽量多换，换剩下的「零头」和新烟的烟蒂合并进入下一轮。复杂度 O(答案 / k)，n 接近 10⁶ 时最多也就跑几十万次，没问题。

这种「模拟到不能换为止」的写法在任何「换东西」的题目里都适用，是最不容易出错的通用解。

三、推导：一步到位的公式

如果想把 O(答案) 压到 O(1)，可以列个方程。设最终抽到 x 根烟，那么：

  • 其中 n 根是直接拿到的；
  • 另外 x − n 根是用烟蒂换来的。

每抽一根烟就会多出一个烟蒂，所以抽完 x 根烟手里就有 x 个烟蒂。

但最后一根烟的烟蒂是换不出新烟的（题目要求「换烟」发生在抽完之后，这一根之后 Peter 就停了）。所以实际「能用来换烟的烟蒂数」是 x − 1。

而这些烟蒂要凑出 x − n 根新烟，每根新烟需要 k 个烟蒂，所以：

1
x - n = (x - 1) / k

两边同乘 k：

1
k * (x - n) = x - 1

展开：

1
2
3
4
kx - kn = x - 1
kx - x = kn - 1
x * (k - 1) = kn - 1
x = (kn - 1) / (k - 1)

把它化成「整除友好」的形式（避免浮点）：

1
x = n + (n - 1) / (k - 1)

验证一下样例 n = 3, k = 2：x = 3 + (3 - 1) / (2 - 1) = 3 + 2 = 5 ✅。

四、O(1) 代码

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    cout << n + (n - 1) / (k - 1);
    return 0;
}

只用三次加法、一次除法，没有循环。

五、为什么 O(1) 公式可以一次到位

while 循环和 O(1) 公式本质是同一个过程——只是把循环展开成了「直接算出总共换到了多少根烟」。所以这两个写法得到的答案完全一样：

n k 公式 n + (n-1)/(k-1) 模拟结果
3 2 3 + 2/1 = 5 5
10 3 10 + 9/2 = 14 14
100 5 100 + 99/4 = 124 124

实测 Python 一行就能对上：

1
2
3
4
5
6
7
8
9
10
11
def peter(n, k):
    total, butts = n, n
    while butts >= k:
        new = butts // k
        total += new
        butts = butts % k + new
    return total

print(peter(3, 2))    # 5
print(peter(10, 3))   # 14
print(peter(100, 5))  # 124

六、边界与极端情况

  1. k = 1：每抽 1 根烟就能换 1 根，理论上 Peter 抽不完。题目保证 k ≥ 2，所以不会出现 k - 1 = 0 的除零；但写代码时还是要心里有数——k = 1 时这个公式没意义。
  2. n = 1：手里只有 1 根烟、1 个烟蒂，k ≥ 2 换不成新烟，答案就是 1。代入公式 1 + 0 / (k - 1) = 1 ✅。
  3. n = k：每抽 k 根烟能换 1 根，烟蒂刚好凑够。但 n - 1 个烟蒂也能凑出 1 个新烟，所以答案是 n + 1。例如 n = k = 3：抽 3 根得 3 个烟蒂 → 换 1 根 → 抽完又得 1 个烟蒂，共 4 根。代入公式 3 + (3 - 1) / (3 - 1) = 3 + 1 = 4 ✅。
  4. long long 防溢出：n, k ≤ 10⁶ 时答案最大约为 10⁶ × 2 = 2 × 10⁶，int 都够用。但 O(1) 公式里 n * k 等中间量如果以后扩展到 n, k ≤ 10⁹ 就会爆，保险起见都开 long long。

七、易错点清单

  1. 少 1 的细节：要记住「最后一根烟的烟蒂不能换」——这是「方程左右差 1」的根源。
  2. k = 1 的除零：题目保证 k ≥ 2，但自己造数据测试时要绕开。
  3. 公式 vs 循环：写循环不容易出错，写公式容易把 n - 1 漏成 n。两种写法都备着，互相验证。
  4. butts % k 别忘了：换完后剩下的「零头」烟蒂要保留进下一轮，否则会少算。
  5. n = 1, k = 2 测一下：最最简单的边界，输出必须是 1。能验证 while 进入条件 butts >= k 正确、n + (n-1)/(k-1) 不越界。

八、小结

这类「手里有 n 个东西，每 k 个换 1 个」问题的标准两步走：

  1. 模拟版本：循环 while (have >= k)，每轮换到新物品，旧物品余数 + 新物品进下一轮。写起来慢但稳；
  2. 公式版本：列「抽到 x 根」与「换出 x − n 根」的等式，注意「最后一个不能换」，化简后一次性算出。写起来快，但要小心 k = 1 等边界。

两道写法互相验证，复杂数据 / 极端样例都可以放心过。