#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 52 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]$