题目详情题解（0）讨论（0）提交记录（0）

CF2075A.To Zero

入门

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两个整数 nn 和 kk，其中 kk 是不小于 33 的奇数。你的任务是将 nn 变为 00。

为此，你可以执行以下操作任意次数：从 11 到 kk 中选择一个数 xx，并将其从 nn 中减去。但需注意：

  • 若当前 nn 是偶数（能被 22 整除），则 xx 也必须是偶数；
  • 若当前 nn 是奇数（不能被 22 整除），则 xx 也必须是奇数。

在不同操作中，可以选择相同的 xx 值，但没有强制要求。因此，重复使用相同的 xx 没有限制。

请计算将 nn 变为 00 所需的最少操作次数。

输入格式

第一行包含一个整数 tt（1≤t≤100001 \le t \le 10000）——测试用例的数量。

每个测试用例占一行，包含两个整数 nn 和 kk（3≤k≤n≤1093 \le k \le n \le 10^9，且 kk 为奇数）。

输出格式

对于每个测试用例，输出一个整数——将 nn 变为 00 所需的最少操作次数。

输入输出样例

  • 输入#1

    8
39 7
9 3
6 3
999967802 3
5 5
6 5
999999999 3
1000000000 3

    输出#1

    7
4
3
499983901
1
2
499999999
500000000

说明/提示

第一个示例中，可以按以下步骤操作：

  1. 从 3939 中减去 55（奇校验），得到 3434；
  2. 执行五次减去 66（偶校验）的操作，得到 44；
  3. 最后减去 44，得到 00。

第二个示例中，可以：

  1. 先减去 33（奇校验）一次；
  2. 再执行三次减去 22（偶校验）的操作。

第三个示例中，可以直接执行三次减去 22（偶校验）的操作。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页