P8046 [COCI 2015/2016 #4] CHEWBACCA

**Problem T3 of this contest set is [P8053](https://www.luogu.com.cn/problem/P8053).**

A $k$-ary tree with $n$ nodes is constructed in the following way: - First, create a root node and label it as $1$. - Then repeat the following steps until the total number of nodes is exactly $n$: - Let the label of the last newly added node be $x$. - In the previous level, scan from left to right to find the first node whose number of children is $< k$. - If this node has no children, add a child node under it, label it as $x + 1$, and connect node $x + 1$ and the parent node we found with an edge of length $1$. - Otherwise, add a new child node immediately to the right of the most recently added child of this node, label it as $x + 1$, and connect node $x + 1$ and the parent node we found with an edge of length $1$. - If no node with number of children $< k$ is found in the current level, move to the next level. For example, the figure below shows a $3$-ary tree with $9$ nodes constructed by the method above:  Now you are given this $k$-ary tree with $n$ nodes, and you need to answer $q$ queries. Each query gives two integers $x, y$, and you need to output the length of the shortest path from node $x$ to node $y$ in this tree.

The first line contains three integers $n, k, q$, representing the number of nodes in the tree, the arity, and the number of queries. Then follow $q$ lines, each containing two integers $x, y$, representing the two nodes in the query.

Output $q$ lines, each containing one integer, the length of the shortest path between node $x$ and node $y$.

**[Sample 1 Explanation]** The figure below shows the tree constructed in sample 1:  It is easy to see that for the $1$st and $2$nd queries, since node $2$ is a child of node $1$, the shortest path length between these two nodes is exactly $1$. For the $3$rd query, one shortest path is $4\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 7$. Therefore, the shortest path length is $4$. **[Sample 2 Explanation]** The tree constructed in sample 2 can be found in the “Description” section. **[Constraints]** For $20\%$ of the testdata, $1\leqslant n, q\leqslant 1000$ is guaranteed. For $50\%$ of the testdata, $1\leqslant n\leqslant 10^5$ is guaranteed. For all testdata, $1\leqslant n\leqslant 10^{15}$, $1\leqslant k\leqslant 1000$, $1\leqslant q\leqslant 10^5$. **[Source]** This problem comes from **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T4 CHEWBACCA_**. Using the original problem’s data configuration, the full score is $120$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5