← 返回题目列表

Codeforces · 2072/G

G. 我翻了300年的数字并计算了总和

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

经过三百年的史莱姆养殖,秋人终于获得了神奇的数字$$$n$$$。到达商人后,他想用号码换取黄金,但商人给了英雄一个任务。

商人说,这个任务需要技能$$$\text{rev}(n, p)$$$,这是秋人最近学到的,巧合的是。 $$$\text{rev}(n, p)$$$ 表示以下过程:

  1. 将数字$$$n$$$写入基数$$$p$$$,令该表示形式为$$$n = \overline{n_{\ell - 1} \ldots n_1 n_0}$$$,其中$$$\ell$$$是数字$$$n$$$的基数$$$p$$$表示形式的长度。
  2. 反转基本 $$$p$$$ 表示,令其为 $$$m = \overline{n_0 n_1 \ldots n_{\ell - 1}}$$$。
  3. 将数字 $$$m$$$ 转换回十进制并将其作为结果返回。

商家的任务是计算总和 $$$x = \sum\limits_{p = 2}^{k} \text{rev}(n, p)$$$。由于这个数字可能相当大,因此只需要 $$$x$$$ 除以 $$$10^9 + 7$$$ 后的余数。商人还提到,之前的旅人已经计算了这个数字三百年了,还没有算完。但你会帮助秋人更快地完成它,对吗?

输入

第一行包含数字 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

在每个测试用例的唯一行中,给出了两个数字 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5, 2 \le k \le 10^{18}$$$) — 神奇数字和求和的上限。

请注意 总和 $$$n$$$ 所有测试用例都不受限制.

输出

对于每个测试用例,您需要输出一个数字 - $$$x = \sum\limits_{p = 2}^{k} \text{rev}(n, p)$$$ 除以 $$$10^9 + 7$$$ 的余数。

示例

输入
复制

12
3 2
42 52
1 10
4 4
16 2
69 69
9 3
19 84
9982 44353
100000 1000000007
17 30
777 1000000000000000000

输出
复制

3
7594
9
6
1
33471
10
2006
120792461
584502117
775
46058362

注意

在第三个测试用例中,$$$n = 1$$$。任何数字系统中的数字一均由单个数字表示,这意味着对于任何 $$$p \ge 2$$$,$$$\text{rev}(1, p) = 1$$$。因此,$$$x = \sum\limits_{p = 2}^{k} 1 = \sum\limits_{p = 2}^{10} 1 = 10 - 2 + 1 = 9$$$。

在第四个测试用例中,$$$x = \text{rev}(4, 2) + \text{rev}(4, 3) + \text{rev}(4, 4)$$$。让我们计算每一项:

  • $$$4 = 100_2 \rightarrow \text{rev}(4, 2) = 001_2 = 1$$$
  • $$$4 = 11_3 \rightarrow \text{rev}(4, 3) = 11_3 = 4$$$
  • $$$4 = 10_4 \rightarrow \text{rev}(4, 4) = 01_4 = 1$$$
因此,$$$x = 1 + 4 + 1 = 6$$$。

在第七个测试用例中,$$$x = \text{rev}(9, 2) + \text{rev}(9, 3)$$$。让我们计算每一项:

  • $$$9 = 1001_2 \rightarrow \text{rev}(9, 2) = 1001_2 = 9$$$
  • $$$9 = 100_3 \rightarrow \text{rev}(9, 3) = 001_3 = 1$$$
因此,$$$x = 9 + 1 = 10$$$。