103493: [Atcoder]ABC349 D - Divide Interval

Problem Statement

For non-negative integers $l$ and $r$ $(l < r)$, let $S(l, r)$ denote the sequence $(l, l+1, \ldots, r-2, r-1)$ formed by arranging integers from $l$ through $r-1$ in order. Furthermore, a sequence is called a good sequence if and only if it can be represented as $S(2^i j, 2^i (j+1))$ using non-negative integers $i$ and $j$.

You are given non-negative integers $L$ and $R$ $(L < R)$. Divide the sequence $S(L, R)$ into the fewest number of good sequences, and print that number of sequences and the division. More formally, find the minimum positive integer $M$ for which there is a sequence of pairs of non-negative integers $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ that satisfies the following, and print such $(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)$ are good sequences.

It can be shown that there is only one division that minimizes $M$.

Constraints

• $0 \leq L < R \leq 2^{60}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$L$ $R$

Output

Print the answer in the following format:

$M$
$l_1$ $r_1$
$\vdots$
$l_M$ $r_M$

Note that the pairs $(l_1, r_1), \dots, (l_M, r_M)$ should be printed in ascending order.

Sample Input 1

3 19

Sample Output 1

5
3 4
4 8
8 16
16 18
18 19

$S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)$ can be divided into the following five good sequences, which is the minimum possible number:

• $S(3,4)=S(2^0\cdot 3,2^0\cdot4)=(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)$

Sample Input 2

0 1024

Sample Output 2

1
0 1024

Sample Input 3

3940649673945088 11549545024454656

Sample Output 3

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

问题描述

对于非负整数$l$和$r$（$l < r$），令$S(l, r)$表示按顺序排列的从$l$到$r-1$的整数序列$(l, l+1, \ldots, r-2, 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$的划分是唯一的。

约束

• $0 \leq L < R \leq 2^{60}$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$L$ $R$

输出

以以下格式打印答案：

$M$
$l_1$ $r_1$
$\vdots$
$l_M$ $r_M$

请注意，对$(l_1, r_1), \dots, (l_M, r_M)$应该按**升序**打印。

样例输入1

3 19

样例输出1

5
3 4
4 8
8 16
16 18
18 19

$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\cdot4)=(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)$

样例输入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