如果一个数 x 的约数和 y （不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x 。例如 4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。 输入 输入一个正整数 n
输出 输出不断进行数字变换且不出现重复数字的最多变换步数。
样例输入 7 样例输出 3
提示 样例说明 一种方案为 4→3→1→7 数据范围与提示 对于 100% 的数据，1≤n≤50000
分析： 首先用类似于筛法的方法求出每个数的约数和，然后看到这种x成为y，y成为x的形式就想到构造无向图，并且因为1的约数和（不算自己）等于0所以不从1往外连边，每个数至多连出一条边，所以最后我们可以得到一棵树，然后这棵树的最长链长度（树的直径）就是答案
代码：
#include<bits/stdc++.h> using namespace std; const int N=100005; int n,s[N]; int d[N],vis[N],head[N],nxt[N],tot=0; inline void add(int x,int y) {vis[++tot]=y,nxt[tot]=head[x];head[x]=tot;} void dfs(int v){ for(int i=head[v];i;i=nxt[i]) if(!d[vis[i]]) { d[vis[i]]=d[v]+1; dfs(vis[i]); } } int main(){ cin>>n; for(int i=1;i<=n/2;i++) for(int j=i+i;j<=n;j+=i) s[j]+=i; for(int i=2;i<=n;i++) if(s[i]<i) add(i,s[i]),add(s[i],i); int m=1; memset(d,0,sizeof(d)); dfs(1); for(int i=1;i<=n;i++) if(d[i]>d[m]) m=i; memset(d,0,sizeof(d)); dfs(m); for(int i=m=1;i<=n;i++) if(d[i]>d[m]) m=i; cout<<d[m]; return 0; }