【资料图】

题目描述

如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y也可以变成 x。例如，4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数 n。

输出格式

输出不断进行数字变换且不出现重复数字的最多变换步数。

数据范围

1≤n≤50000

输入样例

7

输出样例

3

样例解释

一种方案为：4→3→1→7。

题目分析

代码实现

#include#include#includeusing namespace std;#define int long longconst int N=5e4+5,M=2*N;int h[N],e[M],ne[M],idx;int sum[N],vis[N],ans;void add(int x,int y){e[idx]=y,ne[idx]=h[x],h[x]=idx++;}int dfs(int u,int f){    //标记该结点已被访问vis[u]=1;int dist=0,d1=0,d2=0;for(int i=h[u];~i;i=ne[i]){int j=e[i];//防止回头if(j==f)continue;//求当前结点向下的路径int dis=dfs(j,u)+1;//更新该结点向下的最长路径dist=max(dist,dis);//更新最长路径和次长路径if(dis>d1)d2=d1,d1=dis;else if(dis>d2)d2=dis;}//答案即为每个结点的最长路径和次长路径之和的最大值ans=max(ans,d1+d2);return dist;}signed main(){int n;cin>>n;memset(h,-1,sizeof h);//遍历一下，将i*j的约数和算出来for(int i=1;i<=n/2;i++){for(int j=2;j<=n/i;j++)sum[i*j]+=i;}//如果约数之和比本身小，则建立无向边for(int i=2;i<=n;i++){if(sum[i]