題目 3165:
藍橋杯2023年第十四屆省賽真題-子樹的大小
時間限制: 3s
內(nèi)存限制: 320MB 提交: 902 解決: 153
題目描述
給定一棵包含 n 個結點的完全 m 叉樹，結點按從根到葉、從左到右的順序依次編號。
例如下圖是一個擁有 11 個結點的完全 3 叉樹。
你需要求出第 k 個結點對應的子樹擁有的結點數(shù)量。
輸入格式
輸入包含多組詢問。
輸入的第一行包含一個整數(shù) T ，表示詢問次數(shù)。
接下來 T 行，每行包含三個整數(shù) n, m, k 表示一組詢問。
輸出格式
輸出 T 行，每行包含一個整數(shù)表示對應詢問的答案。
樣例輸入
3 1 2 1 11 3 4 74 5 3
樣例輸出
1 2 24
提示
對于 40% 的評測用例，T ≤ 50，n ≤ 106，m ≤ 16 ；
對于所有評測用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109 。