T4
有一个 \(n\) 个节点构成的完全图，第 \(i\) 个点和第 \(j\) 个点连接边权为 \(\text{lcm}(i,j)\) 的边。你需要求出这个完全图的最大生成树的边权和对 \(10^9+7\) 取模的结果。
\(1\le n\le 10^9\)
结论是 \(x\) 与最大的与 \(x\) 互质的数连边，枚举优化加上 \(O(1)\) 求 \(\gcd\) 在赛时可以过 \(10^7\)。
考虑 \(\le n\) 最大的质数 \(p\) 不会离 \(n\) 过远，反正肯定有 \(n-p+1\le 100\)，也就是所有数连的边肯定集中在后 \(100\) 数之内。
后 \(n-p+1\) 个数之间直接单独考虑，前 \(p-1\) 个数考虑容斥。
一开始让所有数连向 \(n\)，从大到小枚举 $i\in[p,n] $，考虑每次将连向 \(i\) 且与 \(i\) 不互质的数连向 \(i-1\)（直到 \(p\)这样的数就会变为 \(0\) 个），也就是与 \(i,i+1,\dots,n\) 都不互质的数的和。
现在就是求有与 \(i,i+1,\dots n\) 都不互质的数的和。这里竟然可以直接使用记忆化搜索。枚举与 \(x\) 的 \(\gcd\) 中的素因子有哪些，根据个数求系数为 \(1\) 或 \(-1\)，现在就是 \(a_i|x,a_{i+1}|x,\dots,a_n|x\)，也就是 \(\text{lcm}(a_i,a_{i+1},\dots,a_n)|x\)，然后按层 dfs，每次记录层数以及目前 \(\text{lcm}\)。