题目描述
请看题解,觉得应该解释的很详细,不清楚的地方欢迎留言讨论,也肯请各位大佬指正代码不足的地方,感谢感谢
时间复杂度
O(t*(logk + logn))
C++ 代码
//1、先判断 k 属于第几层,并计算出该层的第一个数是多少,
// 容易得到每层的第一个节点是上一层第一个节点的值 + (m^上一层的层数),
//2、然后算多少层不够分配剩余的节点(sum)的个数,然后这一层的上一层到第k个k节点的下一层都是满的
//3、然后查询第k个节点所在的这一层它前面的节点是否用光了剩余的节点数量
//4、如果没有就加上,要注意min(qpow(m,i) / m ,sum) //取容纳的最大值和剩余节点数量两个数的最小值
#include <bits/stdc++.h>
#define endl '\n'
#define IOSCC ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef long long ll;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
void solve() {
ll n, m, k;
cin >> n >> m >> k;
vector<ll> f(32); //10^9 < 2^32所以最多32层 (从第0层开始计算)
f[0] = 1;
for (int i = 1; i <= 32; i++) {
f[i] = f[i - 1] + qpow(m, i - 1);
}
ll sum = n;
ll level = 0; //计算出k所在测层数
ll tmp = 0;
for (int i = 0; k > m * tmp + 1; i++){ //log
level = i + 1;
tmp = m * tmp + 1;
}
ll fulllevel = 0; //计算出有多少层是满层的
for (int i = 0; qpow(m, i) <= sum; i++) { //log
sum -= qpow(m, i);
fulllevel = i;
}
ll res = (qpow(m, fulllevel + 1 - level) - 1) / (m - 1); //计算出该节点有多少个满层节点
if (sum == 0) { //如果sum为0,则不用继续下面的计算
cout << res;
return;
}
//开始计算最后一层满层的下一层如何分配节点
//可以发现k所在的哪一行和它所在行的第一个节点的差值影响k节点所在树的最后一层节点
// 与最后一层节点开头的差值:需要多乘上m^(k-f[level])
ll bt = fulllevel + 1; //最后一层是第几层
ll btfi = f[bt]; //最后一层的开头的节点编号
//计算出最后一层前面差了多少个节点
ll diff = qpow(m, bt - level) * (k - f[level]);
//最后就需要判断k所在子树的前面的子树是否将sum消耗完
if (sum > diff) {
res += min(sum - diff, qpow(m, bt - level));
}
cout << res;
}
int main() {
IOSCC;
int _ = 1;
cin >> _;
while (_--) {
solve();
cout << endl;
}
return 0;
}