【題目描述】
如果一個數?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->xst[i] = true;//x可以作為根 }//約數和比自身小}for (int i = 1; i <= n; i++) {if (!st[i]) {//i不能作為根 dfs(i);}}cout << ans << endl;return 0;
}
