题目描述

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

输入格式

输入一个正整数 n。

输出格式

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

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=5e4,M=1e6;
//struct edge{
//	int to,w,nxt;
//}e[M+20];
int cnt,head[N+20],vis[N+20],ans,f[N+20];
vector<int> G[N+20];
//void add(int u,int v,int w){
//	e[++cnt].to=v;
//	e[cnt].w=w;
//	e[cnt].nxt=head[u];
//	head[u]=cnt;
//}
int fun(int x){
	int sum=0,y=sqrt(x);
	for(int i=1;i<=y;i++){
		if(x%i==0) sum+=(i+x/i);
	}
	return sum-x-(y*y==x?y:0);
}
void dfs(int u,int fa){
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(vis[v]) continue;
		vis[v]=1;
		dfs(v,u);
//		cout<<u<<' '<<v<<' '<<f[v]+1<<' '<<f[u]<<endl;
		f[u]=max(f[u],f[v]+1);
		vis[v]=0;
		
	} 
}
void init(){
	for(int i=1;i<=n;i++){
		int sum=fun(i);
		if(sum<i){
			G[i].push_back(sum);
			G[sum].push_back(i);
		}
	}
}
signed main(){
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);
		vis[i]=1;
		dfs(i,0);
	} 
	int ans=0;
//	for(int i=0;i<=n;i++){
//		cout<<i<<':'<<G[i].size()<<'|';
//		for(int j=0;j<G[i].size();j++) cout<<G[i][j]<<' ';
//		puts(""); 
//	}
	for(int i=0;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans<<endl; 
	return 0;
}