AT_abc349_d [ABC349D] Divide Interval

题目描述

对于非负整数 $l,r\ (l < r)$，将从 $l$ 到 $r-1$ 的整数按顺序排列成数列 $(l, l+1, \ldots, r-2, r-1)$，记作 $S(l, r)$。另外，使用非负整数 $i, j$，可以表示成 $S(2^{i}j, 2^{i}(j+1))$ 的数列被称为“好数列”。

给定非负整数 $L, R\ (L < R)$。请将数列 $S(L, R)$ 分割成尽可能少的“好数列”，并输出分割的个数以及分割的方法。更严格地说，求满足以下条件的非负整数对序列 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ 的最小正整数 $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), \dots, (l_M, r_M)$ 需要按升序输出。

输入输出样例 #1

输入 #1

3 19

输出 #1

5
3 4
4 8
8 16
16 18
18 19

输入输出样例 #2

输入 #2

0 1024

输出 #2

1
0 1024

输入输出样例 #3

输入 #3

3940649673945088 11549545024454656

输出 #3

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

说明/提示

约束条件

• $0 \leq L < R \leq 2^{60}$
• 输入均为整数

样例解释 1

$S(3, 19) = (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)$。可以分割为以下 $5$ 个好数列，这也是使分割个数最小的方法。

• $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)$

由 ChatGPT 4.1 翻译