Comet OJ 夏季歡樂賽（2019）A 完全k叉樹??

歡迎報考JWJU！這里有豐富的社團活動，比如為夢想奮斗的ACM集訓隊，經常組織飛行棋的桌游協會，喜歡“唱，跳，rap，籃球”的籃球協會，更奇特的是——讓人耳目一新的攀樹協會。顧名思義，攀樹協會會經常組織大家攀爬一些樹，比如李超樹，左偏樹，帶花樹，智慧樹等等。經過社團組織的一番培訓后，同學們已經學會了如何在樹上的相鄰結點中來回爬動。

不過上述的樹太沒意思了，RegenFallenRegenFallen同學向往更刺激的挑戰，今天他要挑戰的項目是一棵完全 kk 叉樹。

完全kk叉樹的定義：一個 mm 層的完全 kk 叉樹的前 m-1m?1 層均為滿 kk 叉樹，且第 mm 層的結點全部聚集在樹的左側。

因為RegenFallenRegenFallen是一個持久的男人，所以他希望一次能爬盡量長的路徑（不走重復的點），所以他想讓你告訴他，假如現在有一棵 nn 個點的完全 kk 叉樹，每條邊的長度均為 11，從樹上的某一點到另一點的最大距離是多少。

Input

第一行給出一個 tt (t≤10^{4}t≤10
4 ) 代表測試用例的組數。接下來t行，每行包含兩個正整數 k, nk,n (1 \le k \le 10^9, 2 \le n \le 10^91≤k≤10 9 ,2≤n≤10 9 ) 意義如題面所示。

Output

對于每個測試用例，輸出一行一個正整數表示答案。

Examples

樣例輸入 1

1
2 3
樣例輸出 1

2

Hint

題意:

題解:

感覺標程寫的很不錯, 這里貼一下, cometoj的比賽還是蠻不錯的

經驗小結:

看到完全二叉樹的題目優先思維題

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stdlib.h> #include <vector> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> using namespace std; #define ms(x, n) memset(x,n,sizeof(x)); typedef long long LL; const int inf = 1<<30; const LL maxn = 1e5+10;int main() {LL T, k, n, now, cnt;cin >> T;while(T--){cin >> k >> n;if(k == 1){cout << n-1 << endl;continue;}cnt = 0, now = 1;while(n > 0){n -= now;now *= k;++cnt;if(n < now)break;}if(n == 0)cout << (cnt-1)*2 << endl;else if(n <= now/k)cout << cnt*2-1 << endl;elsecout << cnt*2 << endl;}return 0; }```\

總結

以上是生活随笔為你收集整理的【题解】Comet OJ 夏季欢乐赛（2019）A 完全k叉树⭐⭐ 【思维】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。