数字转换
如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。
例如，4 可以变为 3，1 可以变为 7。
限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
输入格式
输入一个正整数 n。
输出格式
输出不断进行数字变换且不出现重复数字的最多变换步数。
数据范围
1≤n≤50000
输入样例：
7输出样例：
3样例解释
一种方案为：4→3→1→7。
分析：每一个x最多向它的约数之和y连一条边，每一个点x最多有一个父节点，y是x的父节点，则y与x之间的连线会构成一棵树（y->x,以1为根节点的树）
另外，在求解每个x的约数之和y时，可用筛法求解
#include <iostream> #include <algorithm> using namespace std; const int N = 50000+10; int sum[N]; int head[N],nexts[N*2],ver[N*2],edge[N*2]; int tot,ans; void add(int x,int y){ ver[++tot]=y; nexts[tot]=head[x],head[x]=tot; } int dfs(int x){ int d1=0,d2=0; for(int i=head[x];i;i=nexts[i]){ int y=ver[i]; int d=dfs(y)+1; if(d>d1){ d2=d1; d1=d; } else if(d>d2){ d2=d; } } ans=max(ans,d1+d2); return d1; } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ //j从2开始循环，所以sum[i]不会加上i for(int j=2;j<=n/i;j++){ sum[i*j]+=i; } } for(int i=2;i<=n;i++){ if(sum[i]<i){ add(sum[i],i); } } dfs(1); printf("%d",ans); return 0; }
