Lazy Numbers
Contest: CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2900
Tags: binary search, math

You are given positive integers $$$n$$$ and $$$k$$$. For each number from $$$1$$$ to $$$n$$$, we write its representation in the number system with base $$$k$$$ (without leading zeros) and then sort the resulting array in lexicographic order as strings. In the sorted array, we number the elements from $$$1$$$ to $$$n$$$ (i.e., indexing starts from $$$1$$$). Find the number of values $$$i$$$ such that the representation of number $$$i$$$ is at the $$$i$$$-th position in the sorted array of representations.

Examples of representations: $$$1$$$ in any number system is equal to $$$1$$$, $$$7$$$ with $$$k = 3$$$ is written as $$$21$$$, and $$$81$$$ with $$$k = 9$$$ is written as $$$100$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. This is followed by a description of the test cases.

The only line of each test case contains integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq k \leq 10^{18}$$$).

Output format:
For each test case, output a single integer — the number of values $$$1 \leq i \leq n$$$ such that the representation of number $$$i$$$ in the number system with base $$$k$$$ is at the $$$i$$$-th position after sorting.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, for numbers $$$1$$$ and $$$2$$$, their representations are at positions $$$1$$$ and $$$2$$$ respectively.

In the second test case, the sorted array is $$$[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$$$, and only the representations of numbers $$$1$$$ and $$$2$$$ are at the required positions.

In the third test case, the sorted array is $$$[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$$$, and only the number $$$1$$$ is at its position.

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

Example output:
2
2
1
3
1
3789
1
7

Editorial:
Let's store all the number entries in a trie. Consider two traversals of this trie - depth-first search (DFS) and breadth-first search (BFS). In both traversals, we go to the children of a node in ascending order of the number on the edge (in the trie). Let the index of the node representing the number $$$x$$$ in the DFS traversal be $$$dfs(x)$$$, and in the BFS traversal be $$$bfs(x)$$$. Then notice that $$$x = bfs(x)$$$, as in BFS on the trie, we simply look at all the number entries with a certain length in order (lengths are concidered in increasing order). On the other hand, $$$dfs(x)$$$ is the index of the number entry $$$x$$$ in the sorted array. Therefore, we want to calculate the number of $$$x$$$ for which $$$dfs(x) = bfs(x)$$$.
Let's fix a layer in the trie, meaning we only consider numbers with a fixed, equal length of representation. Then let's look at $$$dfs(x) - bfs(x)$$$ for the numbers in this layer. Notice that for two numbers $$$y$$$ and $$$y + 1$$$ in this layer, it holds that $$$bfs(y + 1) - bfs(y) = 1$$$, and $$$dfs(y + 1) - dfs(y) \geq 1$$$. This means that for a fixed layer, the function $$$dfs(x) - bfs(x)$$$ is non-decreasing. Therefore, we can find the $$$0$$$ of this function using binary search on each layer.
Now let's learn how to calculate $$$dfs(x) - bfs(x)$$$. $$$bfs(x) = x$$$, which we can calculate. To find $$$dfs(x)$$$, we can traverse up from the trie node corresponding to $$$x$$$, and at each step, add the sizes of the subtrees that we have traversed in DFS before the subtree with the node $$$x$$$.
The trie has a depth of $$$O(\log(n))$$$, binary search takes the same time, so the overall asymptotic complexity of the solution is $$$O(\log^3(n))$$$.
I apologize for the issues some participants faced with the time limit, if they implemented the author's idea suboptimally.