题目描述

如果一个数 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                 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] + d2[i];49     } 50     printf("%d",ans);51     return 0;52 }