题目：树论。
首先观察 f 函数，若 j 为 i 的因数，那么 f(i,j)=\frac{i}{j} 否则 f(i,j)=\frac{i\times f(j,i \ \mathrm{mod} \ j)}{i\ \mathrm{mod} \ j}，对于每一个点 i 我们都把他们存在边权更小的边上。
然后使用贪心的思想，对于每一个大于 1 的节点 i，我们需要找到一个节点 j 使得 \frac{f(i,j)+f(j,i)}{2} 最小。
具体的对于每一个 i 我们都连接到他的最大真因子 j，这个时候边权就是 \frac{i}{j} 也就是 i 的最小质因子，有人问为什么一定是连通的，很简单：
- 对于素数 i，其一定连接到 1。
- 若 i 为合数，则对应的 j 一定小于它，也就是说 j 在 i 之前已经连过一条边，归纳可知 (i,j) 这条边一定连接到 1，所以连通。
然后我们可以使用欧拉筛来实现找到每个节点的最小质因子，这里复杂度就是 O(n)：
void solve(int n){
for(int i=2;i<=n;i++){//i是质数
if(!p[i]){
p[i]=i;
pp.push_back(i);
}
for(int it:pp){
if(i*it>n)break;
p[i*it]=it;//p是i*p的最小质因数
if(i%it==0)break;//确保每个合数只被其最小质因数筛一次
}
}
}
然后就是构造一个最小生成树了，我们把每个大于 1 的节点 i 连接到节点 j=\frac{1}{\mathrm{p}(i)} 上，其中 \mathrm{p}(i) 表示 i 的最小质因子。
伪代码：
/*输入*/
solve(n);//预处理最小的质因子
for(int i=2;i<=n;i++){
int p_=p[i];//i的最小质因数
int j=i/p_;//i的最大真因数
sum+=p_;//边权为 p
g.push_back({j,i});//添加边(j,i)
}
/*输出*/
