分数: 400 点
问题陈述
给你整数 X,Y,和一个整数 K 那至少 2.
有一个变量 x,最初是 x=X。您可以执行以下操作 x 零次或多次:
- 选择一个整数 y 满意 \displaystyle \left\lfloor \frac xK \right\rfloor=y or \displaystyle \left\lfloor \frac yK \right\rfloor=x,并替换值 x 与 y.
在这里, \displaystyle \left\lfloor z \right\rfloor 定义为不超过的最大整数 z,对于实数 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
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
的 i-th (1\le i\le T) 测试用例 \text{case}_i 按以下格式给出:
X Y K
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
4 11 9 3 0 0 2 842 180 7 1948706013487601 48019760148910476 89014537
示例输出 1
2 0 7 5
考虑第一个测试用例。
通过执行以下操作, x=Y 可以通过两种操作来实现:
- 选择 y=3。自从 \displaystyle\left\lfloor\frac{x}K \right\rfloor=\left\lfloor\frac{11}3 \right\rfloor=3,此选择有效。然后,将值替换为 x 与 3.
- 选择 y=9。自从 \displaystyle\left\lfloor\frac{y}K \right\rfloor=\left\lfloor\frac{9}3 \right\rfloor=3,此选择有效。然后,将值替换为 x 与 9.
x=Y 无法通过少于两次操作来实现,因此输出 2 在第一行。