DEGREE - Số lượng bậc
Tác giả: RR
Ngôn ngữ: C++
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;
const double PI = acos(-1.0);
long long power[33], c[33][33];
long long get(long long x, int k, int gh) {
if (x == 0) {
if (k) return 0;
else return 1;
}
if (x < 0) { return 0; }
if (k == 0) return 1;
if (k < 0) return 0;
if (k > gh+1) return 0;
if (gh < 0) return 0;
// cout << x << " " << k << " " << gh << endl;
long long sum = 0;
REP(i,k) sum += power[gh-i];
if (sum <= x) {
// cout << "get = " << c[gh+1][k] << endl;
return c[gh+1][k];
}
long long res = 0;
if (x >= power[gh]) res = get(x-power[gh], k-1, gh-1);
res += get(x, k, gh-1);
// cout << "get = " << res << endl;
return res;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
c[0][0] = 1;
FOR(i,1,32) {
c[i][0] = 1;
FOR(j,1,i)
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
long long x, y, b;
int k, gh;
cin >> x >> y;
cin >> k >> b;
gh = 0; power[gh] = 1;
while (power[gh] <= y) {
gh++;
power[gh] = power[gh-1] * b;
}
gh--;
cout << get(y,k,gh) - get(x-1,k,gh);
return 0;
}