题解 P1150 【Peter的烟】

· · 题解

目前最高赞的答案讲解过略。知道这种题的人自然知道，不知道这种题的人还是不知道。所以我在这里为不知道这种类型题的同学讲一下具体细节。

设最终Peter抽到了x根烟，则其中(x-n)根烟都是用烟蒂换来的，而由于Peter最终能抽x根烟，所以他自始至终共拥有过x个烟蒂。能明白不？

明白了这一点，再想一个细节：实际上Peter抽到的最后一根烟的烟蒂是不能用来换烟的——所以实际可能用来换烟的烟蒂只有(x-1)个。

列出关于换来的烟的数量的方程：

x-n=\frac{x-1}{k}

为了解出x的值，我们解这个方程（这个你应该会叭！）；这才得到了结果式：

kx-kn=x-1 x=\frac{nk-1}{k-1}=\frac{nk-n+n-1}{k-1}=n+\frac{n-1}{k-1}

之所以化成了最后的形式单纯是因为三次加法和一次除法比两次加法、一次乘法和一次除法要省那么一丢丢时间。

下面是程序：

#include <iostream>

int main() {
    unsigned n, k;
    std::cin >> n >> k;
    std::cout << n + (n - 1) / (k - 1) << '\n';
}