xr 的最小生成树
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
xr 有一个 $n$ 个点（点的编号为 $1 \sim n$ 的完全图
对于任意两点 $i,j$ ，这两点之间的边长为 $lcm(i + 1,j + 1)$
xr 最近刚学习了 $Kruskal$ 算法，他自己计算出了这个最小生成树，但是他希望你帮他验证一下他的结果是否正确
所以请你计算一下这个图的最小生成树的边权值总和是多少
当然因为数据过大，所以将结果对 $MOD$ 取模
注：
1. 完全图：即任意两个点之间都存在一条边
2. $lcm$ 表示最小公倍数
3. 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部 $n$ 个顶点，但只有足以构成一棵树的 $n-1$ 条边。
一颗有 $n$ 个顶点的生成树有且仅有 $n-1$ 条边，如果生成树中再添加一条边，则必定成环。
4. 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
输入格式
输入第一行包含一个整数 $T$ 表示共有 $T$ 组测试数据
接下来 $T$ 行，每行包含两个整数 $n,MOD$ 含义如题
对于 $40\%$ 的数据，$1 \leq T \leq 5,n \leq 10^4$
对于 $100\%$ 的数据，$1 \leq T \leq 50,n \leq 10^7, 10^8 \leq MOD \leq 10^{10}$，且保证 $MOD$ 是质数
输出格式
对于每组测试数据，输出一行包含一个整数，表示对 $MOD$ 取模以后的答案
样例
2
3 99999773
100 9999977310
630720230325提高组集训
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-3-25 17:00
- 结束于
- 2023-4-4 17:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 13
