2557 - 幂次求和-东方博宜OJ

题目描述

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

输入

第一行包含两个整数 $X$ 和 $Y$ ，接下来两行包含整数 $K$ 和 $B$ 。

输出

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

样例

15 20
2
2

说明

对于全部数据， $1$ ≤ $X$ ≤ $Y$ ≤ $2$ ^$31$− $1$ , $1$ ≤ $K$ ≤ $20$ , $2$ ≤ $B$ ≤ $10$ 。

标签

题目参数

上一题下一题