【AtCoder】ABC 465 D - X to Y

2026-07-07

AtCoder/ABC/D問題 AtCoder/ABC/400点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/数学/競技プログラミング

D - X to Y

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 839 / NoviSteps: 1Q / 配点: 400 点

問題概要

整数 $X,Y$ と $2$ 以上の整数 $K$ が与えられる。

変数 $x$ があり、はじめ $x=X$ である。これから、 $x$ に対して以下の操作を $0$ 回以上何回でも行うことを考える。

$\displaystyle \left\lfloor \frac{x}{K} \right\rfloor=y$ または $\displaystyle \left\lfloor \frac{y}{K} \right\rfloor=x$ を満たす整数 $y$ を選び、 $x$ の値を $y$ に置き換える。

$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}$

考察

$x, y$ ともに $K$ で割るのは変わらないので、とりあえず $X, Y$ をそれぞれ $K$ で割り続けてみる。

例えばサンプルケース1の3番目のテストケースなら、

\begin{align*} 842 & \to 120 \to 17 \to 2 \to 0 \\ 180 & \to 25 \to 3 \to 0 \end{align*}

この場合、 $x = X = 842$ から上の遷移をたどって一旦 $x = 0$ までもっていき、その後下の遷移に移って $x = Y = 180$ まで戻すことができるので、操作回数は $7$ 回となる。

したがって、 $X = Y$ となるまで「両者の大きい方を $K$ で割った商に置き換える」操作を繰り返し、その回数を記録すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.// ======================================== //
7. 
8.ll solve() {
9.    ll X, Y, K;
10.    cin >> X >> Y >> K;
11. 
12.    ll ans = 0;
13.    while (X != Y) {
14.        if (X > Y) X /= K;
15.        else Y /= K;
16. 
17.        ans++;
18.    }
19. 
20.    return ans;
21.}
22. 
23.int main()
24.{
25.    int T;
26.    cin >> T;
27. 
28.    while (T--) {
29.        cout << solve() << endl;
30.    }
31. 
32.    return 0;
33.}