题解：P11180 [ROIR 2018 Day2] 删除数字

zhujiangyuan · 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;
}