AcWing 4971. 子树的大小
原题链接
困难
作者:
_小镇做题家
,
2024-03-14 20:31:24
,
所有人可见
,
阅读 111
思维, 推公式
from sys import stdin
for _ in range(int(input())):
n, m, k = map(int, input().split())
if k == 1:
print(n)
continue
fi, length = 1, 1
while True:
if fi <= k <= min(fi + length - 1, n): break
fi += length
length *= m
cnt, l, r = 1, k, k
while True:
l = l + (fi + length - 1 - l) + (l - fi) * m + 1
r = min(n, r + (fi + length - 1 - r) + (r - fi) * m + m)
if l > n: break
cnt += r - l + 1
if r == n: break
fi += length
length *= m
print(cnt)