求给定区间 [XXX,YYY] 中满足下列条件的整数个数:这个数恰好等于 KKK 个互不相等的 BBB 的整数次幂之和。例如,设 X=15X=15X=15,Y=20Y=20Y=20,K=2K=2K=2,B=2B=2B=2,则有且仅有下列三个数满足题意:
171717=222444+222000
181818=222444+222111
202020=222444+222222
第一行包含两个整数 XXX 和 YYY,接下来两行包含整数 KKK 和 BBB。
只包含一个整数,表示满足条件的数的个数。
15 20 2 2
3
对于全部数据,111≤XXX≤YYY≤222313131−111, 111≤KKK≤202020,222≤BBB≤101010。
数位DP