"
题目描述
如果一个数 x 的约数和 y （不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。例如 4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
输入格式
输入一个正整数 n。
输出格式
输出不断进行数字变换且不出现重复数字的最多变换步数。
样例
样例输入
7
样例输出
3
样例说明
一种方案为 4→3→1→7。
数据范围与提示
对于 100% 的数据，1≤n≤50000。
**求树的最长链问题，先预处理每个数的约数，将可以互相转化的数之间连边，很明显这是一颗树，我们要求树的最长路径。
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 int sum【50005】 = {0},n,d1【50005】,d2【50005】;
7 void ready()
8 {
9 int i,j;
10 scanf(""%d"",&n);
11 for(i = 1;i <= n;i++)
12 {
13 for(j = 2;j <= n / i;j++)
14 {
15 if(i * j > n)
16 break;
17 sum【i * j】 += i;
18 }
19 }
20 }
21 void dp()
22 {
23 int i;
24 for(i = n;i >= 1;i--) //因为大数字一定是小数字的后代
25 {
26 if(sum【i】 < i) //sum【i】是i的父亲节点
27 {
28 if(d1【i】 + 1 > d1【sum【i】】)//修改sum【i】这点的最大值
29 {
30 d2【sum【i】】 = d1【sum【i】】;
31 //代码效果参考：https://v.youku.com/v_show/id_XNjQwNjU4MTYzMg==.html
d1【sum【i】】 = d1【i】 + 1;32 }
33 else if(d1【i】 + 1 >d2【sum【i】】)
34 {
35 d2【sum【i】】 = d1【i】 + 1;
36 }
37 }
38 }
39 }
40 int main()
41 {
42 int i,ans = 0;
43 ready();
44 dp();
45 for(i = 1;i <= n;i++) //遍历所有的节点，找最大值+次大值的最大值
46 {
47 if(d1【i】 + d2【i】 > ans)
48 ans = d1【i】 + //代码效果参考：https://v.youku.com/v_show/id_XNjQwNjU3MTA3Ng==.html
d2【i】;49 }
50 printf(""%d"",ans);
51 return 0;
52 }
"
