Вам даны натуральные числа $$$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$$$-й позиции после сортировки
82 24 26 433 2532 13780011804570805480 3788366364720306464627 4702032149561577293940402103595405 2
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$$$.
Название |
---|