[Ural 1057]幂和的数量

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file amountofdegrees.in Output file amountofdegrees.out

【题目描述】

写一个程序来计算区间[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