#21802. 数组构造(array)

数组构造(array)

说明


蒟蒻队长最近学习了一种有趣的题型——《构造题》,这种题目是根据题意去构造一组符合规则的输出,有的是序列,有的是数据结构,有的是图和树。

今天蒟蒻队长做了一道基础的题目,这道题的要求如下:
(以下提到的 $i,j$ 满足均 $i < j$)
1. 构造一个尽可能长的数组 $a_i$,在数组中不能有数字重复出现,并且要保证数组元素是升序的,即 $a_i < a_j$
2. 当数组的元素个数 $\geq 2$ 时,对于任意一组 $i,j$ 满足 $a_j \% a_i = 0$
3. 对于任意元素 $a_i$ 满足 $L \leq a_i \leq R$

现在蒟蒻队长已经完成了这道题,但是他不知道他的结果是否正确,所以他希望你帮他计算一下两个问题:1. 最长数组的长度应该是多少,2. 有多少种符合长度最长的数组构造方案?


输入格式

本题采用多组测试数据
输入第一行包含一个正整数 $T$,表示共有 $T$ 组询问
每一行包含一个测试数据
每组测试数据包含两个整数 $L,R$ 表示一组询问的答案

测试数据$T$$L,R$
$1 \sim 4$$1 \leq T \leq 10$$1 \leq L \leq R \leq 100$
$5 \sim 6$$1 \leq T \leq 1000$$1 \leq L \leq R \leq 1000$
$7 \sim 10$$1 \leq T \leq 20000$$1 \leq L \leq R \leq 10^6$

输出格式

输出共 $T$ 行
每行两个整数,分别表示在该组 $L,R$ 所对应的询问最长数组的长度和构造方案数

3
3 11
13 37
1 5
2 4
2 6
3 1

提示

对于第一组测试数据,最长数组长度为 $2$,方案如下
$[3,6],[3,9],[4,8],[5,10]$
对于第二组测试数据,最长数组长度为 $2$,方案如下
$[13,26],[14,28],[15,30],[16,32],[17,34],[18,36]$
对于第三组测试数据,最长数组长度为 $3$,方案如下
$[1,2,4]$

来源

CSP模拟赛