A. 求最少操作次数 - 详细题解

问题重述

给定两个整数 $n$ 和 $k$，每次操作可以减去 $k$ 的任意非负整数次幂（即 $k^0, k^1, k^2, \dots$）。求将 $n$ 变为 $0$ 所需的最少操作次数。

---

关键观察

观察 1：$k = 1$ 的特殊情况

当 $k = 1$ 时，$k$ 的幂次只有 $1^0 = 1$。因此每次只能减去 $1$，最少操作次数为：

$$\text{ans} = n$$

---

观察 2：模 $k$ 的视角

考虑对 $k$ 取模。任何 $k^x$（$x \ge 1$）都是 $k$ 的倍数，因此：

$$k^x \equiv 0 \pmod{k} \quad (x \ge 1)$$

而 $k^0 = 1$，所以：

$$1 \equiv 1 \pmod{k}$$

因此，只有减去 $k^0 = 1$ 的操作会改变 $n$ 模 $k$ 的值。

---

观察 3：处理余数

设 $n = q \cdot k + r$，其中 $0 \le r < k$。

为了将 $n$ 变为 $0$（$0$ 是 $k$ 的倍数），我们需要消除余数 $r$。

由于只有减去 $1$ 才能改变余数，我们必须执行 $r$ 次减去 $1$ 的操作，使 $n$ 变为 $k$ 的倍数：

$$n \to n - r = q \cdot k$$

这 $r$ 次操作是必须的。

---

观察 4：转化为子问题

现在 $n' = q \cdot k$ 是 $k$ 的倍数。考虑以下两种策略：

策略 A：继续减去 $1$（$k^0$）

• 减去 $1$ 后，$n'$ 变为 $q \cdot k - 1$，余数变为 $k-1$
• 需要再减去 $k-1$ 次 $1$ 才能回到 $k$ 的倍数
• 总共 $k$ 次操作，效果相当于减去 $k$（即减去 $k^1$ 一次）

策略 B：直接减去 $k^1 = k$

• 一次操作，$n'$ 变为 $(q-1) \cdot k$

显然，策略 B 更优（$1$ 次操作 vs $k$ 次操作）。

因此，当 $n$ 是 $k$ 的倍数时，最优策略是不断减去 $k$ 本身，相当于将问题规模缩小为 $n/k$。

---

观察 5：递归/迭代过程

将上述过程形式化：

1. 设当前值为 $n$
2. 若 $n = 0$，结束
3. 否则，取 $r = n \bmod k$，需要 $r$ 次减去 $1$ 的操作
4. 然后令 $n = \lfloor n/k \rfloor$，重复步骤 2-4

这实际上就是将 $n$ 表示为 $k$ 进制数，然后求各位数字之和。

---

数学证明

设 $n$ 的 $k$ 进制表示为：

$$n = d_0 + d_1 \cdot k + d_2 \cdot k^2 + \cdots + d_m \cdot k^m $$

其中 $0 \le d_i < k$。

• $d_0$ 是 $n \bmod k$，需要 $d_0$ 次减去 $1$ 的操作
• 减去 $d_0$ 个 $1$ 后，$n$ 变为 $k \cdot (d_1 + d_2 \cdot k + \cdots)$
• 然后可以用一次减去 $k$ 的操作替代 $k$ 次减去 $1$ 的操作
• 这等价于将 $n$ 除以 $k$ 后继续处理

因此，最少操作次数为：

$$\text{ans} = d_0 + d_1 + d_2 + \cdots + d_m = \sum_{i=0}^{m} d_i $$

即 $n$ 在 $k$ 进制下的各位数字之和。

---

算法步骤

1. 如果 $k = 1$，直接输出 $n$
2. 否则，初始化 $ans = 0$
3. 当 $n > 0$ 时：
   • $ans = ans + (n \bmod k)$
   • $n = \lfloor n/k \rfloor$
4. 输出 $ans$

---

完整代码

#include <bits/stdc++.h>
using namespace std;

int find_min_operations(int n, int k) {
    if (k == 1) return n;
    
    int ans = 0;
    while (n > 0) {
        ans += n % k;
        n /= k;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << find_min_operations(n, k) << "\n";
    }
    
    return 0;
}

---

时间复杂度

• 每个测试用例：$O(\log_k n)$
• 总复杂度：$O(t \cdot \log_k n)$，其中 $t \le 10^4$

---

示例验证

测试用例 1：$n = 5, k = 2$

$5$ 的二进制表示为 $101_2$，各位数字和 $= 1 + 0 + 1 = 2$

输出：$2$ ✓

测试用例 2：$n = 3, k = 5$

$3$ 的五进制表示为 $3_5$，各位数字和 $= 3$

输出：$3$ ✓

测试用例 3：$n = 16, k = 4$

$16$ 的四进制表示为 $100_4$，各位数字和 $= 1 + 0 + 0 = 1$

输出：$1$ ✓

测试用例 4：$n = 100, k = 3$

$100$ 的三进制表示：$100 \div 3 = 33$ 余 $1$，$33 \div 3 = 11$ 余 $0$，$11 \div 3 = 3$ 余 $2$，$3 \div 3 = 1$ 余 $0$，$1 \div 3 = 0$ 余 $1$

得到数字：$1, 0, 2, 0, 1$，从低位到高位：$10201_3$

各位数字和 $= 1 + 0 + 2 + 0 + 1 = 4$

输出：$4$ ✓

测试用例 5：$n = 6492, k = 10$

$6492$ 的十进制各位数字和 $= 6 + 4 + 9 + 2 = 21$

输出：$21$ ✓

测试用例 6：$n = 10, k = 1$

$k = 1$，直接输出 $n = 10$

输出：$10$ ✓

---

关键公式总结

$$\boxed{\text{最少操作次数} = \text{将 } n \text{ 表示为 } k \text{ 进制后的各位数字之和}} $$$$\boxed{\text{特殊情况：当 } k = 1 \text{ 时，答案为 } n}$$