【题目描述】
如果一个数 xx 的约数和 yy （不包括他本身）比他本身小，那么 xx 可以变成 yy ，yy 也可以变成 xx 。例如 44 可以变为 33 ，11 可以变为 77 。限定所有数字变换在不超过 nn 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
【输入】
输入一个正整数 nn 。
【输出】
输出不断进行数字变换且不出现重复数字的最多变换步数。
【输入样例】
7【输出样例】
3【提示】
样例说明
一种方案为 4→3→1→74→3→1→7 。
数据范围与提示：
对于 100100 的数据，1≤n≤500001≤n≤50000 。
#include<bits/stdc++.h>
using namespace std;
const int N = 50010, M = 2 * N;
int h[N], e[N], ne[M], idx;
int sum[N];
bool st[N]; //记录树根
int n;
int ans;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}//a,b间加边(a单加b边)
int dfs(int u) {
int d1 = 0, d2 = 0;//最长 次长
for (int i = h[u]; i != -1; i = ne[i]) {//枚举所有u的下一个节点
int j = e[i];//下一个节点
int d = dfs(j) + 1;//找到各种的最长值
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;//改变最大次大
}
ans = max(ans, d1 + d2);//最大答案
return d1;//返回最长值
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= n / i; j++) {
sum[j * i] += i;
}
}//求每个数的约数和
for (int i = 2; i <= n; i++) {
if (i > sum[i]) {
add(sum[i], i);//y->x
st[i] = true;//x可以作为根
}//约数和比自身小
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {//i不能作为根
dfs(i);
}
}
cout << ans << endl;
return 0;
}