题解：P8046 [COCI 2015/2016 #4] CHEWBACCA

题目给了我们一个完全 \(k\) 叉树，但是 \(n \le 10 ^ {15}\)。

我们就可以观察一下每一个点与它的父节点的关系。

假设目前枚举到节点 \(u\)，那么 \(u\) 的父节点编号就为 \(\frac{u + k - 2}{k}\)。所以我们每次对编号大的那个点进行操作，一步一步向上跳即可。

下面是代码环节：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, k, q;
signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k >> q;while (q --) {int x, y;cin >> x >> y;int ans = 0;while (x != y) {if (x < y) {swap(x, y);}x = (x + k - 2) / k;ans ++;}cout << ans << "\n";}return 0;
}