← 返回题目列表

AtCoder · abc349_d

G. 除法间隔

中文机器翻译题面 查看原题

分数: 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