← 返回题目列表

Codeforces · 1870/F

F. 懒惰的数字

中文机器翻译题面 查看原题

给定正整数 $$$n$$$ 和 $$$k$$$。对于从 $$$1$$$ 到 $$$n$$$ 的每个数字,我们以 $$$k$$$ 为基数(不带前导零)编写其在数字系统中的表示形式,然后按字典顺序将结果数组排序为字符串。在排序后的数组中,我们对元素进行编号,从 $$$1$$$ 到 $$$n$$$ (即索引从 $$$1$$$ 开始)。查找值 $$$i$$$ 的数量,使得数字 $$$i$$$ 的表示位于表示排序数组中的第 $$$i$$$ 个位置。

表示示例:任何数系中的 $$$1$$$ 都等于 $$$1$$$,$$$7$$$ 与 $$$k = 3$$$ 写为 $$$21$$$,$$$81$$$ 与 $$$k = 9$$$ 写为 $$$100$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的唯一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq k \leq 10^{18}$$$)。

输出

对于每个测试用例,输出一个整数 - 值的数量 $$$1 \leq i \leq n$$$,使得数字 $$$i$$$ 在以 $$$k$$$ 为基数的数字系统中的表示形式在排序后位于第 $$$i$$$ 位置。

示例

输入 #1

8
2 2
4 2
6 4
33 2
532 13
780011804570805480 3788
366364720306464627 4702032149561577
293940402103595405 2

输出 #1

2
2
1
3
1
3789
1
7

注意

在第一个测试用例中,对于数字 $$$1$$$ 和 $$$2$$$,它们的表示分别位于位置 $$$1$$$ 和 $$$2$$$ 处。

在第二个测试用例中,排序后的数组为 $$$[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$$$,并且只有数字 $$$1$$$ 和 $$$2$$$ 的表示位于所需位置。

在第三个测试用例中,排序后的数组为 $$$[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$$$,只有数字 $$$1$$$ 位于其位置。