分数: 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