题目描述

给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序依次编号。

例如下图是一个拥有 11 个结点的完全 3 叉树。

你需要求出第 k 个结点对应的子树拥有的结点数量。

输入格式

输入包含多组询问。

输入的第一行包含一个整数 T ，表示询问次数。

接下来 T 行，每行包含三个整数 n, m, k 表示一组询问。

输出格式

输出 T 行，每行包含一个整数表示对应询问的答案。

样例输入

3
1 2 1
11 3 4
74 5 3

样例输出

1
2
24

提示

对于 40% 的评测用例，T ≤ 50，n ≤ 10^6，m ≤ 16 ；

对于所有评测用例，1 ≤ T ≤ 10^5，1 ≤ k ≤ n ≤ 10^9，2 ≤ m ≤ 10^9 。

#include<iostream>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		int n,m,k;
		scanf("%lld%lld%lld",&n,&m,&k);
		bool flag=1;
		int cnt=1;
		int l=k,r=k;
		while(flag){//迭代计算k节点的子节点个数
			l=(l-1)*m+2;//最左边子节点的编号
			r=r*m+1;//最右边子节点的编号
			if(r>n){
				r=n;
				flag=0;
			}
			if(l<=n) cnt+=r-l+1;
		}
		printf("%lld\n",cnt);
	}
	return 0;
}