3165 問題 F: 藍橋杯2023年第十四屆省賽真題-子樹的大小
時間限制: 2s
內(nèi)存限制: 256MB 提交: 902 解決: 153
題目描述
給定一棵包含 n 個結(jié)點的完全 m 叉樹，結(jié)點按從根到葉、從左到右的順序依次編號。
例如下圖是一個擁有 11 個結(jié)點的完全 3 叉樹。
你需要求出第 k 個結(jié)點對應(yīng)的子樹擁有的結(jié)點數(shù)量。
輸入
輸入包含多組詢問。
輸入的第一行包含一個整數(shù) T ，表示詢問次數(shù)。
接下來 T 行，每行包含三個整數(shù) n, m, k 表示一組詢問。
輸出
輸出 T 行，每行包含一個整數(shù)表示對應(yīng)詢問的答案。
樣例輸入
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 。
比賽公告
加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油