题目描述
原题题面
求给定区间 中满足下列条件的整数个数：这个数恰好等于 个互不相等的 的整数次幂之和。例如，设 ，则有且仅有下列三个数满足题意：
输入格式
第一行包含两个整数 和 ，接下来两行包含整数 和 。
输出格式
只包含一个整数，表示满足条件的数的个数。
样例输入
15 20
2
2
样例输出
3
【解题思路】：
因为所求数为互不相等的幂之和，因此其B进制表示的各位数字均只能为0或1，所以可转化为二进制进行求解。
【AC代码】：
#include<cstdio>
#include<algorithm>
using namespace std;inline void read(int &x){
char ch=getchar(),c=ch;x=0;while(ch<'0' || ch>'9'){
c=ch;ch=getchar();}while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}if(c=='-')x=-x;
}int dp[32][32],a[32];
int K,B,X,Y;void init(){
//预处理f数组 dp[0][0]=1;for(int i=1;i<=31;i++){
dp[i][0]=dp[i-1][0];for(int j=1;j<=i;j++)dp[i][j]=dp[i-1][j]+dp[i-1][j-1];}
}int calc(int x, int k){
//统计区间[0,x]内二进制表示含k个1的数的个数 int tot=0,ans=0,len=0,i;//tot记录当前路径上已有的1的数量，ans为答案 while(x){
a[++len]=x%B;x/=B;}for(i=len;i>0;i--){
if (a[i]==1) {
ans+=dp[i-1][k-(tot++)];if(tot==k)break;} else if(a[i]>1){
ans+=dp[i][k-tot];break;}}return tot==k?ans+1:ans;
}int main(){
read(X),read(Y);read(K),read(B);init();printf("%d\n",calc(Y,K)-calc(X-1,K));//因为calc(Y,K)求解的是区间[0,Y]中满足条件的数的个数，所以求解[X,Y]区间答案时需相减return 0;
}