分数: 450 点
问题陈述
对于非负整数 l 和 r (l < r),让 S(l, r) 表示序列 (l, l+1, \ldots, r-2, r-1) 通过排列整数形成 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.
约束
- 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