問題一覧 > 通常問題

No.2287 ++ -- *=a /=a

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : みここみここ / テスター : cureskolcureskol sapphire__15sapphire__15 👑 potato167potato167
0 ProblemId : 9170 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-26 18:34:42

問題文

非負整数 $x, y$ と $2$ 以上の整数 $a$ が与えられます。

はじめ黒板には $x$ が書かれています。これに対しあなたは以下のいずれかの操作を何回でも行うことができます(一度も行わなくても良いです)。

  • 黒板に書かれた整数 $z$ を $z + 1$ に書き換える。
  • 黒板に書かれた整数 $z$ を $z - 1$ に書き換える。ただし $z = 0$ のときこの操作を行うことはできない。
  • 黒板に書かれた整数 $z$ を $z \times a$ に書き換える。
  • 黒板に書かれた整数 $z$ を $\lfloor \frac{z}{a} \rfloor$ に書き換える。

黒板に書かれた整数を $y$ にするために必要な操作回数の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

$T$
test$_1$
$\vdots$
test$_T$

ただし test$_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。

$x \ y \ a$
  • 入力される値はすべて整数
  • $1 \le T \le 10^4$
  • $0 \le x, y \le 10^{18}$
  • $2 \le a \le 10^{18}$

出力

$T$ 行出力してください。$i$ 行目には $i$ 個目のテストケースの答えを出力してください。

サンプル

サンプル1
入力
4
7 4 2
20 11 10
12093298 4893042 23
0 0 2
出力
2
4
41
0

一つ目のテストケースでは、以下のようにして $2$ 回の操作で黒板に書かれた整数を $4$ にすることができます。

  1. $7$ を $7 + 1 = 8$ に書き換える。
  2. $8$ を $\lfloor \frac{8}{2} \rfloor = 4$ に書き換える。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。