← 返回题目列表

AtCoder · abc290_g

G. 边缘消除

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

分数: 600 点

问题陈述

解决以下问题 T 测试用例。

我们有一个完美的 K深度二叉树 D (与 1+K+K^2+\dots+K^D 顶点)。
你的目标是切割一些边以获得一个连通分量 X 顶点。
至少必须切割多少条边才能达到目的?

约束

  • 输入中的所有值都是整数。
  • 1 \le T \le 100
  • 1 \le D
  • 2 \le K
  • \displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}

输入

输入由标准输入按以下格式给出:

T
case_1
\vdots
case_T

在这里, case_i 表示 i- 第一个测试用例。
每个测试用例均按以下格式给出:

D K X

输出

打印 T 行。
的 i- 第行应包含以下问题的答案 i- 第一个测试用例作为整数。


样本输入 1

11
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
1 999999999999999999 1
1 999999999999999999 2
1 999999999999999999 999999999999999999
1 999999999999999999 1000000000000000000

示例输出 1

1
2
1
1
2
1
0
1
999999999999999998
1
0