AcWing1081 - 度的数量
求给定区间 [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K 个互不相等的 B 的整数次幂之和。
例如,设 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:
17=24+20 18=24+21 20=24+22
输入格式
第一行包含两个整数 X 和 Y,接下来两行包含整数 K 和 B。
输出格式
只包含一个整数,表示满足条件的数的个数。
数据范围
1≤X≤Y≤231−1, 1≤K≤20, 2≤B≤10
输入样例:
1
2
3
15 20
2
2
输出样例:
1
3
按位分情况讨论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
#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() - 1; 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;
}
last++;
if (last > K) break;
}
if (!i && last == K) res++;
}
return res;
}
int main() {
init();
int l, r;
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
This post is licensed under CC BY 4.0 by the author.