在进制区间 [a,b]
逐个进制 p
枚举,生成在该进制下所有符合“两个不同数字交替出现(含单个数字)”的数,转换为十进制后落在 [l,r]
的集合。
设长度为 n
的交替串最高位为 A(≠0)
,另一位为 B(≠A)
。把该数写成:
value = A * S_even(p,n) + B * S_odd(p,n)
其中
形如 1212121 这种由不同的 2 个数字交替出现的数称为波浪数,k 重波浪数则是指在 k 种不同的进制下都是波浪数的数。特别规定只有一位的数字(如 1 )也是波浪数。例如,下面这个数字是一个四重波浪数(下标表示采用的进制): $606_{(7)}=454_{(8)}=363_{(9)}=300_{(10)}=1A1_{(13)}$ 需要注意的是,本题描述下的数字交替出现并不局限于阿拉伯数字 0−9 。当进制较大时需要使用字符代表数字,如 16 进制下使用 A、B、C、D、E、F 字符代表十进制下的数字 10、11、12、13、14、15 。在上面给出的例子中,我们认为 1A1 也是波浪数,13 进制下的数字 1A1 转换为 10 进制的计算方式可以表达为:1∗130+10∗131+1∗132=300 。
接下来,需要你在指定数字区间内根据给定所需要考虑的进制区间找到所有的 k 重波浪数。
五个整数 a,b,l,r,k,其中 [a,b] 表示应当考虑的进制区间,[l,r] 以十进制表示询问的数字区间,k 表示波浪数的重数。
数据范围:2<=a<=b<=32,1<=l<=r<=10000000,k∈{2,3,4}
从小到大按十进制输出所有所求的波浪数,每行一个数字。
输入
2 3 10 15 2
输出
10
说明
样例要求在 2 进制和 3 进制下求 [10,15] 数字区间(十进制)内所有的波浪数。
这个区间内只有一个波浪数 10 (十进制),转化为 2 进制和 3 进制分别为:1010(2)−101(3) 。