#10163. 「一本通 5.3 例 1」Amount of Degrees

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:NEERC 2000 Central Subregional,题面详见 Ural 1057

求给定区间 [X,Y][X,Y] 中满足下列条件的整数个数:这个数恰好等于 KK 个互不相等的 BB 的整数次幂之和。例如,设 X=15,Y=20,K=2,B=2X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:

\begin{align} 17&=2^4+2^0 \\ 18&=2^4+2^1 \\ 20&=2^4+2^2 \end{align}

输入格式

第一行包含两个整数 XXYY,接下来两行包含整数 KKBB

输出格式

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

样例

样例输入

15 20
2
2

样例输出

3

数据范围与提示

对于全部数据,1XY2311,1K20,2B101\le X\le Y\le 2^{31}-1,1\le K\le 20,2\le B\le 10