杭电3 Segment Tree with Pruning

题面：给定n,k,1到n每次分成两段，当段长度小于等于k则停止，求能分成多少段。
解析：分成的段与其左右节点无关，只与区间长度和k有关。所以只要模拟建树和剪枝的过程即可，因为有大量重复的数据，再加上记忆化搜索，可大大降低复杂度。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
map<ll,ll> p;
ll bt(ll n,ll k){
    if(n<=k) return p[n]=1;
    if(p.find(n)!=p.end()) return p[n];
    return p[n]=bt(n/2,k)+bt(n-n/2,k)+1;

}
int main(){
    cin>>t;
    while(t--){
    p.clear();
        cin>>n>>k;
        cout<<bt(n,k)<<endl;

    }
}