Dotcpp  >  编程题库  >  信息学奥赛一本通T1585-Amount of Degrees
题目 2489:

信息学奥赛一本通T1585-Amount of Degrees

时间限制: 2s 内存限制: 192MB 提交: 26 解决: 12

题目描述

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

求给定区间 [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。

输出格式

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

样例输入

15 20
2
2

样例输出

3

提示

数据范围与提示:

对于全部数据,1≤X≤Y≤231−1,1≤K≤20,2≤B≤10。

标签