思路：dp[i][j]:表示第i位在B进制下数字和。
用二分找第k个数！
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 using namespace std; 10 int dp[45][310],b,m,bit[45]; 11 int dfs(int pos,int mm,bool f) 12 { 13 if(pos==-1) return mm==m; 14 if(!f&&dp[pos][mm]!=-1) return dp[pos][mm]; 15 int ans=0; 16 int e=f?bit[pos]:(b-1); 17 for(int i=0;i<=e;i++){ 18 ans+=dfs(pos-1,mm+i,f&&i==bit[pos]); 19 } 20 if(!f) dp[pos][mm]=ans; 21 return ans; 22 } 23 int solve(int n) 24 { 25 if(n<=0) return n==m; 26 int s=0; 27 while(n){ 28 bit[s++]=n%b; 29 n/=b; 30 } 31 return dfs(s-1,0,1); 32 } 33 int main(){ 34 int q,x,y,n,k,ca=0; 35 while(scanf("%d%d%d%d%d",&q,&x,&y,&b,&m)!=EOF){ 36 memset(dp,-1,sizeof(dp)); 37 printf("Case %d: ",++ca); 38 if(x>y) swap(x,y); 39 if(q==1) printf("%d ",solve(y)-solve(x-1)); 40 else{ 41 scanf("%d",&k); 42 int low=solve(x-1); 43 int high=solve(y); 44 if(high-low<k){ 45 puts("Could not find the Number!"); 46 continue; 47 } 48 int l=x,r=y,mid,ans=0; 49 while(l<=r){ 50 mid=(int)(((ll)l+(ll)r)>>1); 51 int t=solve(mid); 52 if(t-low>=k) r=mid-1,ans=mid; 53 else l=mid+1; 54 } 55 printf("%d ",ans); 56 } 57 } 58 return 0; 59 }