Peter 的烟的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算 Peter 在“ $k$ ~k~ 个烟蒂可以换一根新烟”的规则下，从最初的 $n$ ~n~ 根烟出发一共能吸到多少根烟。核心解法是模拟兑换过程：只要手里的烟蒂数不少于 $k$ ~k~ 就换烟，把换得的新烟累加到总根数上，再更新剩余的烟蒂数，直到烟蒂数少于 $k$ ~k~ 为止。

分析

核心观察

每吸完一根烟都会产生 $1$ ~1~ 个烟蒂，所以换来的新烟不需要单独追踪：设当前烟蒂数为 $b$ ~b~，用它们换到的 $x$ ~x~ 根新烟吸完后又会贡献 $x$ ~x~ 个烟蒂，加上换剩下的 $b \bmod k$ ~b \bmod k~ 个，新的烟蒂数就是 $b \bmod k + x$ ~b \bmod k + x~。

思路

设总烟数 $ans$ ~ans~ 与手中的烟蒂数 $b$ ~b~ 都从 $n$ ~n~ 开始，因为最初 $n$ ~n~ 根烟都要吸掉，各自产生 $1$ ~1~ 个烟蒂。只要 $b \ge k$ ~b \ge k~，就执行一次兑换：

$\displaystyle x = \left\lfloor \frac{b}{k} \right\rfloor, \quad ans \leftarrow ans + x, \quad b \leftarrow b \bmod k + x$

其中 $x$ ~x~ 是本轮换到的新烟数， $b \bmod k$ ~b \bmod k~ 是换完后剩下的旧烟蒂， $x$ ~x~ 是这些新烟吸完后新增的烟蒂。当 $b < k$ ~b < k~ 时无法再换，此时的 $ans$ ~ans~ 就是答案。

循环一定会终止：当 $b \ge k$ ~b \ge k~ 时， $b \bmod k \le k - 1$ ~b \bmod k \le k - 1~ 且 $\lfloor b/k \rfloor \le b/k$ ~\lfloor b/k \rfloor \le b/k~，于是 $b \bmod k + \lfloor b/k \rfloor \le (k-1) + b/k \le b$ ，而取等号只可能发生在 $b = k$ ~b = k~ 处，此时新烟蒂数为 $1$ ~1~，仍然严格小于 $b$ ~b~，故烟蒂数每轮都在减少。又因为 $b$ ~b~ 较大时每轮约缩小为原来的 $1/k$ ~1/k~，轮数为 $O(\log_k n)$ ~O(\log_k n)~。

由此还能得到等价的闭式答案：每次兑换净消耗 $k-1$ ~k-1~ 个烟蒂，循环结束时手中必然剩下 $1$ ~1~ 到 $k-1$ ~k-1~ 个无法兑换的烟蒂，因此一共换得 $\lfloor (n-1)/(k-1) \rfloor$ ~\lfloor (n-1)/(k-1) \rfloor~ 根新烟，答案也可写作 $n + \lfloor (n-1)/(k-1) \rfloor$ ~n + \lfloor (n-1)/(k-1) \rfloor~，可以 $O(1)$ ~O(1)~ 直接算出。下面代码采用模拟写法，两者结果完全一致。

具体示例

以 $n = 4$ ~n = 4~、 $k = 3$ ~k = 3~ 为例：初始 $ans = 4$ ~ans = 4~、 $b = 4$ ~b = 4~。第一轮换得 $x = \lfloor 4/3 \rfloor = 1$ ~x = \lfloor 4/3 \rfloor = 1~ 根，于是 $ans = 5$ ~ans = 5~、 $b = 4 \bmod 3 + 1 = 2$ ~b = 4 \bmod 3 + 1 = 2~；此时 $b = 2 < 3$ ~b = 2 < 3~，无法再换，答案为 $5$ ~5~。

再看 $n = 10$ ~n = 10~、 $k = 3$ ~k = 3~：第一轮换得 $x = 3$ ~x = 3~ 根， $ans = 13$ ~ans = 13~、 $b = 1 + 3 = 4$ ~b = 1 + 3 = 4~；第二轮换得 $x = 1$ ~x = 1~ 根， $ans = 14$ ~ans = 14~、 $b = 1 + 1 = 2$ ~b = 1 + 1 = 2~，停止，答案为 $14$ ~14~。用闭式核对得 $10 + \lfloor 9/2 \rfloor = 14$ ~10 + \lfloor 9/2 \rfloor = 14~，二者一致。

算法步骤

读入一组 n 与 k，若输入已经读完则结束。
令 ans 与 b 都等于 n。
当 b 不小于 $k$ ~k~ 时反复执行：令 x 为 $\lfloor b/k \rfloor$ ~\lfloor b/k \rfloor~，把 x 累加到 ans，再把 b 更新为 $b \bmod k + x$ ~b \bmod k + x~。
输出 ans，回到第 $1$ ~1~ 步处理下一组数据。

复杂度分析

时间：每组数据 $O(\log_k n)$ ~O(\log_k n)~，最坏情况出现在 $k = 2$ ~k = 2~ 时，循环次数约为 $\log_2 10^8 \approx 27$ ~\log_2 10^8 \approx 27~。
空间： $O(1)$ ~O(1)~，只用到常数个变量。

实现注意事项

题面以“每组测试数据”为单位描述输入输出，一份输入文件可能包含多行、每行一组 $n$ ~n~ 与 $k$ ~k~，需要循环读入直到文件结束，并为每组数据各输出一行。
循环条件是烟蒂数不小于 $k$ ~k~，不能写成大于 $k$ ~k~：烟蒂数恰好等于 $k$ ~k~ 时仍然可以换到 $1$ ~1~ 根新烟。
更新烟蒂数时要用旧的 $b$ ~b~ 同时算出 $b \bmod k$ ~b \bmod k~ 与 $b / k$ ~b / k~，先求出 $x$ ~x~ 再改写 $b$ ~b~，避免中途覆盖。
答案的最大值出现在 $n = 10^8$ ~n = 10^8~、 $k = 2$ ~k = 2~ 时，为 $199999999$ ~199999999~，仍在 $32$ ~32~ 位有符号整数范围内，不需要更宽的整数类型。
题目保证 $k > 1$ ~k > 1~，烟蒂数每轮严格减少，循环不会陷入死循环，无需额外的步数保护。
每组数据的答案都要单独占一行，注意行末换行。

源代码

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    while (cin >> n >> k) {
        int ans = n;
        int b = n;
        while (b >= k) {
            int x = b / k;
            ans += x;
            b = b % k + x;
        }
        cout << ans << '\n';
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.read().split()
    out = []
    for i in range(0, len(data) - 1, 2):
        n, k = int(data[i]), int(data[i + 1])
        ans = n
        b = n
        while b >= k:
            x = b // k
            ans += x
            b = b % k + x
        out.append(str(ans))
    if out:
        sys.stdout.write("\n".join(out) + "\n")


main()

目前没有评论。