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
| #include <bits/stdc++.h> using namespace std;
const int N = 32; int f[N][N], k, b, l, r, a[N];
int solve(int x) { int ans = 0, tot = 0; for (int i = 31; i; i--) { if (x & (1 << i)) { tot++; if (tot > k) break; x ^= (1 << i); } if (x >= (1 << (i - 1))) ans += f[i - 1][k - tot]; } if (tot + x == k) ans++; return ans; }
int calc(int x, int b) { int cnt = 0; while (x) { a[cnt++] = x % b; x /= b; } int res = 0; for (int i = cnt - 1; i + 1; i--) { if (a[i] > 1) { for (int j = i; j + 1; j--) res |= (1 << j); } else res |= (a[i] << i); } return res; }
int main() { scanf("%d %d %d %d", &l, &r, &k, &b); f[0][0] = 1; for (int i = 1; i < N; i++) { f[i][0] = 1; for (int j = 1; j <= i; j++) f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; } printf("%d\n", solve(calc(r, b)) - solve(calc(l - 1, b))); return 0; }
|