题意简述

你有两个整数 $n$ 和 $k$（$3 \le k \le n$，$k$ 为奇数）。
每次操作，若当前 $n$ 是偶数，只能减去一个偶数 $x$（$1 \le x \le k$）；
若当前 $n$ 是奇数，只能减去一个奇数 $x$（$1 \le x \le k$）。
求最少操作次数使 $n$ 变为 $0$。

---

关键观察

1. 奇偶性变化规律

   • 奇数 $-$ 奇数 $=$ 偶数
   • 偶数 $-$ 偶数 $=$ 偶数

   结论：

   • 若 $n$ 初始为奇数，第一步必须减一个奇数，之后 $n$ 变成偶数。
   • 若 $n$ 初始为偶数，直接进入偶数状态。
   • 一旦 $n$ 变成偶数，它永远保持偶数（因为只能减偶数）。

2. 贪心策略
   为了最小化步数，每次应尽可能减最大的合法数：

   • 奇数状态：最大可减 $k$（$k$ 是奇数）
   • 偶数状态：最大可减 $k-1$（因为 $k$ 是奇数，$k-1$ 是偶数）

3. 特殊情况
   如果在某一步减 $x$ 后 $n$ 会变成负数，我们可以用更小的 $x$ 来正好减到 $0$。
   所以最终一定能到达 $0$。

---

解题步骤

第一步：处理奇数情况

若 $n$ 是奇数：

• 先减 $k$（奇数），$n \leftarrow n - k$，操作数 $+1$
• 此时 $n$ 变为偶数

若 $n$ 初始就是偶数，跳过此步。

第二步：处理偶数情况

现在 $n$ 是偶数，每次最多减 $k-1$（偶数）。
我们要用最少的次数 $m$ 使得：

$$m \cdot (k-1) \ge n$$

因为最后一步可以减小于 $k-1$ 的偶数来恰好到 $0$。

所以：

$$m = \left\lceil \frac{n}{k-1} \right\rceil$$

第三步：向上取整的整数实现

在 C++ 中，整数除法 $a/b$ 是向下取整。
向上取整 $\lceil \frac{a}{b} \rceil$ 可以用：

$$\left\lceil \frac{a}{b} \right\rceil = \frac{a + b - 1}{b} \quad \text{(整数除法)} $$

第四步：总操作数

$$\text{ans} = (\text{奇数处理步数}) + \left\lceil \frac{n_{\text{even}}}{k-1} \right\rceil $$

其中 $n_{\text{even}}$ 是第一步处理后的 $n$（偶数）。

---

标程对应代码

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        
        long long ans = 0;
        
        // 如果 n 是奇数，先减一个 k（奇数），变成偶数
        if (n % 2 == 1) {
            n -= k;
            ans = 1;
        }
        
        // 此时 n 是偶数，每次最多减 k-1（偶数）
        k -= 1;  // 现在 k 代表偶数状态下的最大减数
        
        // 向上取整除法
        ans += (n + k - 1) / k;
        
        cout << ans << endl;
    }
    return 0;
}

---

正确性证明简述

• 奇数第一步必须做：因为奇数只能变偶数，且必须一次减奇数，最大为 $k$，贪心最优。
• 偶数状态：只能减偶数，最大为 $k-1$，所以最少次数就是 $\lceil n/(k-1) \rceil$。
• 最后一步调整：可以减更小的偶数来恰好到 $0$，所以 $m \cdot (k-1) \ge n$ 即可，等号不一定取到。

---

复杂度分析

• 每个测试用例 $O(1)$ 时间
• 总复杂度 $O(t)$，完美通过 $t \le 10^4$ 的数据。

---

示例验证

例：$n=39, k=7$

1. $n$ 奇数 → $n = 39-7=32$，$ans=1$
2. $k=6$（偶数状态最大减数）
3. $\lceil 32/6 \rceil = 6$（因为 $6 \times 5 = 30 < 32$，$6 \times 6 = 36 \ge 32$）
4. 总 $ans = 1+6 = 7$ ✅

---

这样，我们就得到了一个基于奇偶性分析和贪心策略的简洁 $O(1)$ 解法。