#1830. 士兵游戏
士兵游戏
士兵游戏
题目描述
标题: 士兵游戏 - Problem - QOJ.ac
#8953. 士兵游戏
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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
31
样例 2
50
4986