{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"MD","content":"**原题来自:NEERC 2000 Central Subregional,题面详见 [Ural 1057](http://acm.timus.ru/problem.aspx?space\u003d1\u0026num\u003d1057)。**\n\n求给定区间 $[X,Y]$ 中满足下列条件的整数个数:这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。例如,设 $X\u003d15,Y\u003d20,K\u003d2,B\u003d2$,则有且仅有下列三个数满足题意:\n\n$17\u003d2^4+2^0$\n\n$18\u003d2^4+2^1$\n\n$20\u003d2^4+2^2$"}},{"title":"输入格式","value":{"format":"MD","content":"第一行包含两个整数 $X$ 和 $Y$,接下来两行包含整数 $K$ 和 $B$。"}},{"title":"输出格式","value":{"format":"MD","content":"只包含一个整数,表示满足条件的数的个数。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e15 20\n2\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"数据范围与提示","value":{"format":"MD","content":"对于全部数据,$1\\le X\\le Y\\le 2^{31}-1,1\\le K\\le 20,2\\le B\\le 10$。"}}]}