求给定区间 [X,Y][X,Y]
中满足下列条件的整数个数：这个数恰好等于 KK
个互不相等的 BB
的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2X=15,Y=20,K=2,B=2
，则有且仅有下列三个数满足题意：17=24+2017=24+20
18=24+2118=24+21
20=24+2220=24+22
输入格式第一行包含两个整数 XX
和 YY
，接下来两行包含整数 KK
和 BB
。输出格式只包含一个整数，表示满足条件的数的个数。数据范围1≤X≤Y≤231−11≤X≤Y≤231−1
, 1≤K≤201≤K≤20
, 2≤B≤102≤B≤10
输入样例：15 20 2 2 输出样例：3
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 35; int K, B; int f[N][N]; void init(){ for (int i = 0; i < N; i ++) for (int j = 0; j <= i; j ++) if (!j) f[i][j] = 1; else f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; } int dp(int n){ if (!n) return 0; vector<int> nums; while(n) nums.push_back(n % B), n /= B; int res = 0; int last = 0; for (int i = nums.size(); i >= 0; i --){ int x = nums[i]; if (x){ res += f[i][K - last]; if (x > 1){ if (K - last - 1 >= 0) res += f[i][K - last - 1]; break; } else{ last ++; if (last > K) break; } } if (!i && last == K) res ++; } return res; } int main(){ init(); int l, r; scanf("%d%d%d%d", &l, &r, &K, &B); cout << dp(r) - dp(l - 1) << endl; return 0; }