[AtCoder abc465_d] X to Y

涉及知识点：图论、树形结构、$K$-叉树、最近公共祖先 (LCA)、双指针、数学（整除与取模）

问题描述

给你两个整数 $X,Y$，还有一个不小于 $2$ 的整数 $K$。
有一个变量 $x$，初始值是 $x=X$。你可以对 $x$ 执行以下操作任意次（包括零次）：

• 选择一个整数 $y$，满足 $\lfloor \frac{x}{K}\rfloor =y$ 或 $\lfloor \frac{y}{K}\rfloor =x$，然后把 $x$ 的值替换成 $y$。
  这里，$\lfloor z\rfloor$ 表示不大于实数 $z$ 的最大整数。
  请你求出使得 $x=Y$ 的最少操作次数。题目保证在给定条件下，总能用有限步数让 $x=Y$。
  你需要处理 $T$ 组测试数据，每组独立解答。

约束条件

• $1\le T\le 2\times 10^5$
• $0\le X,Y\le 10^{18}$
• $2\le K\le 10^{18}$
• 所有输入均为整数。

输入格式

输入从标准输入读取，格式如下：

T$cas{e}_1$$cas{e}_2$...$cas{e}_T$

第 $i$ 组测试数据 ($1\le i\le T$) 格式为：

X Y K

输出格式

请按顺序输出每组测试数据的答案，每个答案占一行。

样例 1

输入样例 1

411 9 30 0 2842 180 71948706013487601 48019760148910476 89014537

输出样例 1

2075

样例说明

看第一组测试数据。
通过下面的操作，$x=Y$ 可以在两步内完成：

• 选择 $y=3$。因为 $\lfloor \frac{x}{K}\rfloor =\lfloor \frac{11}{3}\rfloor =3$，这个选择合法。然后把 $x$ 的值改成 $3$。
• 选择 $y=9$。因为 $\lfloor \frac{y}{K}\rfloor =\lfloor \frac{9}{3}\rfloor =3$，这个选择合法。然后把 $x$ 的值改成 $9$。
  $x=Y$ 不可能用少于两步完成，所以第一行输出 $2$。

正解代码与思路讲解

算法核心思路

本题的本质是一个经典的**树上两点间最短路径（最近公共祖先 LCA）**问题。
如果我们把每个非负整数看作一个节点，由于任何数不断除以 $K$ 最终都会变成 $0$，所有的数在“除以 $K$”的映射下其实构成了一棵以 $0$ 为根节点的 $K$-叉树。

• 操作 1 ($y=\lfloor x/K\rfloor$)：代表在树上从当前节点向双亲节点移动一步。
• 操作 2 ($\lfloor y/K\rfloor =x$)：代表在树上从当前节点向孩子节点移动一步。
  因此，从 $X$ 变到 $Y$ 的最少操作次数，等价于求在这棵 $K$-叉树中，节点 $X$ 到节点 $Y$ 的最短路径长度。在树中，两点间的最短路径必然经过它们的最近公共祖先 (LCA)。我们只需分别找出 $X$ 和 $Y$ 走到根节点 $0$ 的所有祖先路径，再倒序比对找出它们分叉的位置即可。由于 $X,Y\le 10^{18}$ 且 $K\ge 2$，树的最大深度不超过 ${\log }_2(10^{18})\approx 60$ 层，所以暴力收集路径并查找 LCA 的单次时间复杂度为 $O({\log }_K\max (X,Y))$，效率极高。

正确 AC 代码

1#include <bits/stdc++.h>2using namespace std;3#define int long long4#define endl "\n"5 6void solve() {7    int x, y, k;8    cin >> x >> y >> k;9    vector<int> pathX, pathY;10    // 1. 顺着树枝向上不断除以 k，收集 X 的所有祖先节点（直至根节点 0）11    while (true) {12        pathX.push_back(x);13        x /= k;14        if (pathX.back() == 0) break;15    }16    // 2. 同理，收集 Y 的所有祖先节点17    while (true) {18        pathY.push_back(y);19        y /= k;20        if (pathY.back() == 0) break;21    }22    // 3. 使用双指针从两端路径的末尾（即根节点 0）开始倒序向前比对23    int i = pathX.size() - 1;24    int j = pathY.size() - 1;25    while (i >= 0 && j >= 0) {26        // 只要发现两个祖先不相同，说明找到了分叉点，此时对应的上一个相同节点就是 LCA27        if (pathX[i] != pathY[j]) break;28        i--, j--;29    }30    // 4. 此时 pathX[0...i] 和 pathY[0...j] 是独立的分叉路径31    // 它们各自到 LCA 的距离之和为 (i + 1) + (j + 1)，精简后即为 i + j + 232    cout << i + j + 2 << endl;33}34 35signed main() {36    ios::sync_with_stdio(false);37    cin.tie(0);38    int T = 1;39    cin >> T;40    while (T--) {41        solve();42    }43    return 0;44}

$F(x)$表示抽$k$个$x$倍数的方案数
$F(x)={(}_k^{(cn{t}_x)})$

$G(x)$表示抽k个数$gcd$为$x$的方案数

有$F(d)={\sum }_{d|t}G(t)$

则$G(t)={\sum }_{k=1}^{k\ast t\le V}\mu (k)\ast F(k\ast t)$