要整除。 $n \bmod k = r \ne 0$ 时先减 $r$ 次把它凑成 $k$ 的倍数。
减多了是浪费，减少了除不了，所以恰好减 $r$ 次。
不能除过头。如果 $n/k < m$ ，除完就低于目标，而操作只能让数变小，
再也回不去了。这种情况下只能老老实实地减 $n - m$ 次。

同理，如果「减到最近的 $k$ 的倍数」这一步就会掉到 $m$ 以下，那也直接减到
$m$ 收工。

还有一个退化情况： $k = 1$ 时除以 1 原地踏步，完全没有意义，答案就是
$n - m$ 。不特判的话会死循环。

每除一次，数字至少减半，所以循环次数是 $O(\log n)$ 而不是 $O(n)$ 。

完整代码实现

import sys


def solve() -> None:
    """贪心地「能除就除，除不动就先补到能除」"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n, m, k = int(data[0]), int(data[1]), int(data[2])

    if k == 1:                     # 除法原地踏步，只剩减法
        sys.stdout.write(str(n - m) + "\n")
        return

    ans = 0
    while n > m:
        if n % k == 0:
            if n // k >= m:        # 除完不会越过 m，除是划算的
                n //= k
                ans += 1
            else:                  # 除完就比 m 小了，只能减
                ans += n - m
                break
        else:
            r = n % k              # 先减到最近的 k 的倍数
            if n - r >= m:
                n -= r
                ans += r
            else:                  # 减不到下一个倍数，直接减到 m
                ans += n - m
                break

    sys.stdout.write(str(ans) + "\n")


if __name__ == "__main__":
    solve()

示例推演

以示例 n = 10, m = 4, k = 2 为例：

步骤	当前 $n$	判断	动作	累计操作
1	10	$10 \bmod 2 = 0$ 且 $10/2 = 5 \ge 4$	除以 2， $n = 5$	1
2	5	$5 \bmod 2 = 1$ ，凑整减 1 后 $4 \ge 4$	减 1， $n = 4$	2
3	4	$n = m$ ，结束	—	2

答案 2。如果全程用减法需要 $10 - 4 = 6$ 次，差距很明显。

再看 n = 7, m = 3, k = 2：

步骤	当前 $n$	判断	动作	累计操作
1	7	$7 \bmod 2 = 1$ ， $7-1 = 6 \ge 3$	减 1， $n = 6$	1
2	6	$6/2 = 3 \ge 3$	除以 2， $n = 3$	2

答案 2，比直接减 4 次（ $7-3$ ）更省。

最后看一个「除过头」的例子 n = 10, m = 6, k = 2： $10/2 = 5 < 6$ ，
只要除就会掉到目标以下，所以只能减 $10 - 6 = 4$ 次，答案 4。

复杂度分析

解法	时间复杂度	空间复杂度	说明
一步步减 1 模拟	$O(n - m)$	$O(1)$	$n$ 到 $10^9$ 时必然超时
贪心「能除就除」（本文）	$O(\log_k n)$	$O(1)$	每除一次至少减半

易错点总结

1. 忘了特判 $k = 1$

$n / 1 = n$ ，循环会永远停在原地。 $k = 1$ 时除法没有意义，答案直接是
$n - m$ 。

2. 先除再判断，掉到 $m$ 以下

$n = 10, m = 6, k = 2$ ：先除得到 5，比目标还小，再也回不来。必须
先判断 $n/k \ge m$ 再除。

3. 除不尽时一路减 1

$n = 7, k = 2$ 时一直减到 6 才对，但更省的做法是「减 $n \bmod k$ 次」。
$n$ 可能是 $10^9$ ，逐次减 1 会超时。

4. 循环条件写成 `while n != m`

如果某一步除不动（ $n \bmod k \ne 0$ 且减不到倍数），n 可能永远等于不了
m，会死循环。用 while n > m，并且在两个「只能减」的分支里直接
break。

5. $n = m$ 的答案是 0

不要漏掉这个情况，也不要把答案写成「正整数」就强行返回 1。

扩展思考

如果操作变成「 $+1$ 和 $/k$ 」，方向就反过来了：应当从 $m$ 出发，考虑
「乘 $k$ 还是 $+1$ 」，这是另一道经典题（ $m$ 需要先乘到不超过 $n$ 的最大
$k$ 的幂）。
如果每一步的除数可以自己选，问题就变成「用哪些因子做除法最省」，
适合从大到小枚举 $n$ 的因数。
如果把两种操作看成无权图上的两条边，这题就是 $n$ 到 $m$ 的最短路。
贪心的正确性来自边的方向单一（只会变小）以及除法收益的结构性优势；
一旦允许「变大」的操作，贪心就不成立了，得回到 BFS。
也可以用 $k$ 进制来理解：一次「减到最近的倍数」正好把最低一位清零，代价
等于这一位的数字；一次除法相当于右移一位。所以总操作数大致就是 $n$ 的
$k$ 进制各位数字之和，最后再按 $m$ 做边界修正。