#PQJ1788x8953. QOJ 1788_8953

    ID: 2702 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2022树上算法倍增

QOJ 1788_8953

标题: 士兵游戏 - Problem - QOJ.ac

#8953. 士兵游戏

Statistics

The problem was used in the following contests:

小海对军事很感兴趣,所以今天她找了一款军事游戏来玩。

游戏中,小海的士兵有 n 个驻点,标号为 1, ..., n。为了发展经济,小海在驻点之间建了很多通路,具体来说,对于任意一个标号不为1的驻点i,小海修建了一条连接i和ih(i)且距离为1的双向道路,其中h(i)定义为i的最小质因子。(不难证明,所有驻点会形成一棵树)。

为了保护国家的安全,小海决定每一天让士兵在所有点对间巡逻。当然,巡逻也需要一定的开销,具体来说,在驻点i和驻点j间巡逻的开销为两点间的最短距离。

此时小海想知道每一天巡逻的开销是多少,由于答案太大,你只需要输出答案对109+7取模的结果即可。

具体来说,小海想要知道

∑i=1n−1∑j=i+1ndis(i,j)(mod109+7)

其中dis(i,j)表示的是i和j在这颗树上的最短距离。

输入

一行,一个整数 n,表示驻点数量。

输出

一行,一个整数,表示树的所有点对最短距离和。

样例一

input

6

output

31

样例二

input

50

output

4986

限制与约定

对于100的数据:n≤1010

子任务编号 n≤ 分值 1 105 10 2 5⋅107 35 3 109 25 4 1010 30