← 返回题目列表

Codeforces · 2020/F

F. 计数叶子

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

令 $$$n$$$ 和 $$$d$$$ 为正整数。我们构建除数树 $$$T_{n,d}$$$ 如下:

- 树的根是标有数字 $$$n$$$ 的节点。这是树的第 $$$0$$$ 层。
- 对于从 $$$0$$$ 到 $$$d - 1$$$ 的每个 $$$i$$$,对于第 $$$i$$$ 层的每个顶点,执行以下操作。如果当前顶点标记为 $$$x$$$,则创建其子顶点并使用 $$$x$$$ 的所有可能的不同除数 $$$^\dagger$$$ 标记它们。这些子级将位于 $$$(i+1)$$$-st 层。
- 第 $$$d$$$ 层上的顶点是树的叶子。

例如,$$$T_{6,2}$$$($$$n = 6$$$ 和 $$$d = 2$$$ 的除数树)如下所示:

将 $$$f(n,d)$$$ 定义为 $$$T_{n,d}$$$ 中的叶子数。

给定整数 $$$n$$$、$$$k$$$ 和 $$$d$$$,请计算 $$$\sum\limits_{i=1}^{n} f(i^k,d)$$$,模 $$$10^9+7$$$。

$$$^\dagger$$$ 在这个问题中,如果 $$$y \ge 1$$$ 且存在一个整数 $$$z$$$ 使得 $$$x = y \cdot z$$$,则我们说整数 $$$y$$$ 是 $$$x$$$ 的约数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$d$$$ ($$$1 \le n \le 10^9$$$、$$$1 \le k,d \le 10^5$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^9$$$。

输出

对于每个测试用例,输出 $$$\sum\limits_{i=1}^{n} f(i^k,d)$$$,模 $$$10^9+7$$$。

示例

输入 #1

3
6 1 1
1 3 3
10 1 2

输出 #1

14
1
53

注意

在第一个测试用例中,$$$n = 6$$$、$$$k = 1$$$ 和 $$$d = 1$$$。因此,我们需要找到除数树 $$$T_{1,1}$$$、$$$T_{2,1}$$$、$$$T_{3,1}$$$、$$$T_{4,1}$$$、$$$T_{5,1}$$$、$$$T_{6,1}$$$ 中的叶子总数。

- $$$T_{1,1}$$$ 只有一片叶子,标记为 $$$1$$$。
- $$$T_{2,1}$$$ 有两片叶子,标记为 $$$1$$$ 和 $$$2$$$。
- $$$T_{3,1}$$$ 有两片叶子,标记为 $$$1$$$ 和 $$$3$$$。
- $$$T_{4,1}$$$ 有三片叶子,分别标记为 $$$1$$$、$$$2$$$ 和 $$$4$$$。
- $$$T_{5,1}$$$ 有两片叶子,标记为 $$$1$$$ 和 $$$5$$$。
- $$$T_{6,1}$$$ 有四片叶子,标记为 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$6$$$。

叶子总数为 $$$1 + 2 + 2 + 3 + 2 + 4 = 14$$$。

在第二个测试用例中,$$$n = 1$$$、$$$k = 3$$$、$$$d = 3$$$。因此,我们需要找到 $$$T_{1,3}$$$ 中的叶子数,因为 $$$1^3 = 1$$$。这棵树只有一片叶子,所以答案是$$$1$$$。