传送门
思路：
前置知识——树的直径：
▲定义：找到两个点，使得它们的距离最远，它们的路径就是树的直径。
▲求解：
此类问题，需要求出以每个节点为根的子树中的最长链，取其中的最大值即为该树的最长链。
对于每个节点，都要记录两个值： d1 [ i ] 表示以 i 为根的子树中，i 到叶子节点的距离最大值；d2 [ i ] 表示以 i 为根的子树中，除距离最大值所在子树，i 到叶子节点的最大值。（也就是次大值）。则：
①若 d1[ j ] + dis[ i ][ j ] ＞ d1[ i ]，则 d2[ i ] = d1[ i ]；d1[ i ] = d1[ j ] + dis[ i ][ j ]；
②否则，若 d1[ j ] + dis[ i ][ j ] ＞ d2[ i ]，则 d2[ i ] = d1[ j ] ＋ dis[ i ][ j ]；
最后扫描所有的节点，找最大的 d1 [ i ] + d2 [ i ] 的值，就是树的直径（最长链）。
本题思路：
预处理出每个数的约数，将可以转化的数之间连边。就可以建出一棵树，而所求的最多变换步数即为树的直径。
标程：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<stack> #include<vector> #include<queue> #include<deque> #include<map> #include<set> using namespace std; #define maxn 50001 #define max(a, b) ((a)>(b)?(a):(b)) typedef long long LL; LL sum[maxn],n,d1[maxn],d2[maxn];//sum预处理每个数的约数 LL ans=0; inline LL read() { LL kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } inline void ready() { for(LL i=1;i<=n;i++) for(LL j=2;j<=n/i;j++) { if(i*j>n) break; sum[i*j]+=i; } } inline void dp() { for(LL i=n;i>=1;i--)//因为大数字一定是小数字的后代（逆序） if(sum[i]<i)//表示i为sum[i]的子节点 { if(d1[i]+1>d1[sum[i]])//修改sum[i]的值（操作见上） { d2[sum[i]]=d1[sum[i]]; d1[sum[i]]=d1[i]+1; } else if(d1[i]+1>d2[sum[i]]) d2[sum[i]]=d1[i]+1; } } int main() { n=read(); ready(); dp(); for(LL i=1;i<=n;i++) ans=max(ans,d1[i]+d2[i]);//更新答案 printf("%lld\n",ans); return 0; }