← 返回题目列表

AtCoder · abc465_d

D. X 到 Y

中文机器翻译题面 查看原题

分数: 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 在第一行。