Lazy Numbers
我觉得本题难度在于银剑的构造......
我们把 k 进制下的数去掉前导零放在 Trie 树上,并且越高位的深度越小,这样我们看出某个节点的 dfs 序就是排名,称排名减数值为 va。我们需要求 va=0 的点数。
不难发现某一深度从左往右的 va 单调不降,所以可以二分求出每层的点数。
然后求 dfs 序可以手玩,于是就没了。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll __int128_t
const int UP=65;
int T,dep;
ll n,k,LL[UP],RR[UP],b[UP],Ans;
ll read(){
ll x=0;
char s=getchar();
while(s<'0'||s>'9'){
s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);
s=getchar();
}
return x;
}
void prt(ll va){
if(va>(ll)9) prt(va/10);
putchar(va%10+'0');
}
ll calc(ll x){
ll res=0,tmp=0;int de=0;
while(x){b[++de]=x%k;x/=k;}
for(int i=1;i<=de/2;i++) swap(b[i],b[de-i+1]);
for(int i=1;i<=de;i++){
tmp=tmp*k+b[i];
res+=min(tmp,RR[i])-LL[i]+1;
}
for(int i=de+1;i<=dep;i++){
tmp*=k;
res+=min(tmp-1,RR[i])-LL[i]+1;
}
return res;
}
int main (){
T=(int)read();
while (T--){
n=read();k=read();dep=0;
Ans=(ll)0;
for(ll va=1;va<=n;va*=k){
dep++;
LL[dep]=va;RR[dep]=min(va*k-(ll)1,n);
}
ll mid,res,res1,res2,L,R;
for (ll i=1;i<=dep;i++){
L=LL[i];R=RR[i];
res1=0;res2=0;
while(L<=R){
mid=(L+R)>>(ll)1;
res=calc(mid)-mid;
if(res==(ll)0) res1=mid;
if(res<(ll)0) L=mid+1;
else R=mid-1;
}
if(res1==(ll)0) continue;
L=LL[i];R=RR[i];
while (L<=R){
mid=(L+R)>>(ll)1;
res=calc(mid)-mid;
if(res==(ll)0) res2=mid;
if(res>(ll)0) R=mid-1;
else L=mid+1;
}
Ans+=res2-res1+(ll)1;
}
prt(Ans);printf("\n");
}
return 0;
}