← 返回题目列表

Codeforces · 1891/D

D. 可疑的对数

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

令 $$$f$$$($$$x$$$) 为 $$$x$$$ 的二进制对数的下限。换句话说,$$$f$$$($$$x$$$)是最大的非负整数$$$y$$$,使得$$$2^y$$$不超过$$$x$$$。

设 $$$g$$$($$$x$$$) 为 $$$x$$$ 以 $$$f$$$($$$x$$$) 为底的对数下限。换句话说,$$$g$$$($$$x$$$)是最大的非负整数$$$z$$$,使得$$${f(x)}^{z}$$$不超过$$$x$$$。

您收到 $$$q$$$ 查询。第 $$$i$$$ 查询由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 组成。查询的答案是所有整数 $$$k$$$ 的 $$$g$$$($$$k$$$) 之和,使得 $$$l_i \leq k \leq r_i$$$。由于答案可能很大,请以 $$${10^9 + 7}$$$ 为模打印它们。

输入

第一行包含一个整数 $$$q$$$ — 查询数量 ($$$1 \leq q \leq 10^5$$$)。

接下来的 $$$q$$$ 行每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ — 第 $$$i$$$ 查询的边界 ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$)。

输出

对于每个查询,输出查询模 $$$10^9 + 7$$$ 的答案。

示例

输入 #1

12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625

输出 #1

6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692

注意

下表包含所有 $$$x$$$ 的函数 $$$f$$$($$$x$$$) 和 $$$g$$$($$$x$$$) 的值,使得 $$$1 \leq x \leq 8$$$。

$$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$ 2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$1$$$