如果一个数 xx 的约数之和 yy（不包括他本身）比他本身小，那么 xx 可以变成 yy，yy 也可以变成 xx。 例如，44 可以变为 33，11 可以变为 77。 限定所有数字变换在不超过 nn 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。 输入格式 输入一个正整数 nn。 输出格式 输出不断进行数字变换且不出现重复数字的最多变换步数。 数据范围 1≤n≤500001≤n≤50000 输入样例： 7
输出样例： 3
样例解释 一种方案为：4→3→1→74→3→1→7。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 50010, M = N; int h[N], e[M], w[M], ne[M], idx; bool st[N]; int ans; int sum[N]; int n; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } int dfs(int u){ st[u] = true; int dist = 0; int d1 = 0, d2 = 0; for (int i = h[u]; ~i; i = ne[i]){ int j = e[i]; if (!st[j]){ int d = dfs(j) + 1; dist = max(dist, d); if (d > d1) d2 = d1, d1 = d; else if (d > d2) d2 = d; } } ans = max(ans, d1 + d2); return dist; } int main(){ scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++) for (int j = 2; j <= n / i; j ++) sum[i * j] += i; for (int i = 2; i <= n; i ++) if (sum[i] < i) add(sum[i], i); for (int i = 1; i <= n; i ++) if (!st[i]) dfs(i); cout << ans << endl; return 0; }