← 返回题目列表

Codeforces · 1542/C

C. 奇怪的功能

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

设 $$$f(i)$$$ 表示最小正整数 $$$x$$$,使得 $$$x$$$ 不是 $$$i$$$ 的约数。

计算 $$$\sum_{i=1}^n f(i)$$$ 模 $$$10^9+7$$$。换句话说,计算 $$$f(1)+f(2)+\dots+f(n)$$$ 模 $$$10^9+7$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$),即测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^{16}$$$)。

输出

对于每个测试用例,输出一个整数 $$$ans$$$,其中 $$$ans=\sum_{i=1}^n f(i)$$$ 模 $$$10^9+7$$$。

示例

输入 #1

6
1
2
3
4
10
10000000000000000

输出 #1

2
5
7
10
26
366580019

注意

在第四个测试用例 $$$n=4$$$ 中,因此 $$$ans=f(1)+f(2)+f(3)+f(4)$$$。

- $$$1$$$ 是 $$$1$$$ 的约数,但 $$$2$$$ 不是,因此 $$$2$$$ 是不是 $$$1$$$ 的约数的最小正整数。因此,$$$f(1)=2$$$。
- $$$1$$$ 和 $$$2$$$ 是 $$$2$$$ 的约数,但 $$$3$$$ 不是,因此 $$$3$$$ 是不是 $$$2$$$ 的约数的最小正整数。因此,$$$f(2)=3$$$。
- $$$1$$$ 是 $$$3$$$ 的约数,但 $$$2$$$ 不是,因此 $$$2$$$ 是不是 $$$3$$$ 的约数的最小正整数。因此,$$$f(3)=2$$$。
- $$$1$$$ 和 $$$2$$$ 是 $$$4$$$ 的约数,但 $$$3$$$ 不是,因此 $$$3$$$ 是不是 $$$4$$$ 的约数的最小正整数。因此,$$$f(4)=3$$$。

因此,$$$ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$$$。