OI题库

【题目描述】

写一个程序来计算区间[X,Y]内满足如下条件的整数个数：它恰好等于K个互不相等的B的整数幂之和。

举个例子。令X=15，Y=20，K=2，B=2。在这个例子中，区间[15,20]内有3个整数恰好等于两个互不相等的2的整数幂之和：

17=2^4+2^0

18=2^4+2^1

20=2^4+2^2

【输入格式】

输入文件的第一行有两个空格隔开的整数X,Y（1<=X<=Y<=2^31-1）.

第二行有两个整数K,B（1<=K<=20,2<=B<=10）.

【输出格式】

输出一行一个整数，即[X,Y]中恰好等于K个互不相等的B的整数幂之和的数的个数。

【样例输入】

15 20
2 2

【样例输出】

3

【来源】

Ural 1057 Amount of Degrees

Problem Source: Rybinsk State Avia Academy