4132: 好序列
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
# Divide Interval
## 题目描述
对于非负整数 $l$ 和 $r$ $(l < r)$，令 $S(l, r)$ 表示由 $l$ 到 $r-1$ 的整数按顺序排列形成的序列。此外，当且仅当一个序列可以表示为 $S(2^i j, 2^i (j+1))$ 时，其中 $i$ 和 $j$ 为非负整数，我们称这个序列为好序列。
给定非负整数 $L$ 和 $R$ $(L < R)$。将序列 $S(L, R)$ 划分为最少数量的好序列，并输出划分数量和划分方案。更具体地说，找到最小的正整数 $M$，使得存在一个非负整数对序列 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ 满足以下条件，并输出这样的 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$。
- $L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R$
- $S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M)$ 都是好序列。
可以证明，使 $M$ 最小化的划分方案是唯一的。
输入
## 输入格式
输入$L$和$R$，按以下格式输出答案：
$M$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_M$ $r_M$
输出
## 输出格式
注意，对 $(l_1, r_1), \ldots, (l_M, r_M)$ 应按升序输出。
样例输入 复制
3 19样例输出 复制
5
3 4
4 8
8 16
16 18
18 19提示
## 输入输出样例
### 输入样例1
```
3 19
```
### 输出样例1
```
5
3 4
4 8
8 16
16 18
18 19
```
### 输入样例2
```
0 1024
```
### 输出样例2
```
1
0 1024
```
### 输入样例3
```
3940649673945088 11549545024454656
```
### 输出样例3
```
8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656
```
## 数据范围与提示
【样例1说明】
$S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)$ 可以被划分为以下五个好序列，这是最小可能的数量：
- $S(3,4)=S(2^0\cdot 3,2^0\cdot 4)=(3)$
- $S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)$
- $S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)$
- $S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)$
- $S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)$
【数据范围】
$0 \leq L < R \leq 2^{60}$，所有输入值都是整数。
## 题目来源
ABC349D