题解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4 + 10;

vector<int> g[N];

bool vis[N];

int n,uf,vf,ans,maxn = -2e9,f[N],dep[N];
// f[i] 表示 i 的约数和
// dep[i] 表示以 n 为根的树上 i 节点的深度

void dfs(int u,int fa,int d,int &y){
	dep[u] = d,vis[u] = 1;
	if(d > maxn) y = u,maxn = d;
	for(int v : g[u])
		if(v != fa) dfs(v,u,d + 1,y);
}

signed main(){
	scanf("%lld",&n);
	
	for(int i = 1;i <= n;i++)
		for(int j = i + i;j <= n;j += i)
			f[j] += i;
	// 倍数筛求约数和
	
	for(int i = 2 /*正整数 不包括 1 -> 0*/;i <= n;i++){
		int j = f[i];
		if(j >= i) continue;
		g[i].push_back(j);
		g[j].push_back(i);
		// 加边
	}
	
	for(int i = 1;i <= n;i++){
		if(vis[i]) continue;
		maxn = -2e9;
		dfs(i,i,0,uf);
		maxn = -2e9;
		dfs(uf,uf,0,vf);
		ans = max(ans,maxn);
	}
	
	printf("%lld\n",ans);
	return 0;
}