问题 3370 --度的数量

3370: 度的数量

时间限制: 1 Sec  内存限制: 256 MB
提交: 5  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

求给定区间[X,Y]中满足下列条件的整数个数:这个数恰好等于K个互不相等的B的整数次幂之和。

例如,设 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:

17=2^4+2^0
18=2^4+2^1
20=2^4+2^2

输入

第一行包含两个整数XY,接下来两行包含整数KB

输出

只包含一个整数,表示满足条件的数的个数。

样例输入

15 20
2
2

样例输出

3

提示

1≤X≤Y≤2^31−1

1≤K≤20

2≤B≤10

来源

[提交][状态]