自动搬运

查看原文

来自洛谷，原作者为

	zhujiangyuan AFO.

搬运于2025-08-24 23:04:59，当前版本为作者最后更新于2024-10-10 08:50:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这不就是 P9748 [CSP-J 2023] 小苹果 的第 $2$ 问？

考虑第 $n$ 项被删除时一定满足当前 $n \bmod k=0$，所以我们模拟删除数字的过程，每次删掉 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 个数，当 $n \bmod k=0$ 时输出删除次数。

该题并不会存在 $n$ 不被删除的情况，所以并不会输出 $0$。

证明：对于数字 $i$，若 $i<k$，$i$ 必然不会删除，但是只有当前数字个数小于 $k$ 时才停止，所以 $i\ge k$ 的数必然被删除。又因为题面上规定 $k<n$，所以 $n$ 一定会被删除。

关于复杂度：推一下式子能够得到删除次数 $T>\log_{\frac{k}{k-1}}\frac{n}{k}$ 时，一定会停止删除。当 $n=10^{18}$ 且 $k=100$ 时，这个值大概是 $3665$，足以通过此题。

cin >> n >> k;
while (n) {
    cnt ++;
    if (n % k == 0) return cout << cnt << '\n', 0;
    n -= n / k;
}