题目链接

1、问题转化
若x能变成y，那么就在x和y之间建立一条无向边，边权为1，因此每个x都只会向其约数和y至多建1条边，这符合树的形式，y是x的父亲。
所有的x都向各自的y建一条边，最后会构成一个森林（多棵树）。对这些树求树的最大直径就是答案。
树的直径

2、如何建图
要想在x和y之间建一条无向边，就要知道x的约数有哪些。

最暴力的做法就是对每个x，枚举其约数1至$\sqrt{n}$
这样的做法是$O(n\sqrt{n})$。有超时的风险。

可以用类似筛法的思想，枚举$i$从$1$到$n$，将$i$放入$2i、3i、4i...$的合数中。
这样的做法是$O(nlogn)$。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 50005;
int n, sum[N], ans;
int nxt[2 * N], lnk[2 * N], head[2 * N], idx;
bool visit[N];

void add(int a, int b) {
	lnk[idx] = b;
	nxt[idx] = head[a];
	head[a] = idx ++ ;
}

int dfs(int node) {
	visit[node] = true;
	int dis, d1 = 0, d2 = 0;
	
	for (int i = head[node]; i != -1; i = nxt[i]) {
		int son = lnk[i];
		if (!visit[son]) {
			dis = dfs(son) + 1;
			if (d1 <= dis) d2 = d1, d1 = dis;
			else if (d2 < dis) d2 = dis;
		}
	}
	
	ans = max(ans, d1 + d2);
	return d1;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 2; j <= n / i; j ++ ) {
			sum[i * j] += i;
		}
	}
	memset(head, -1, sizeof head);
	for (int i = 1; i <= n; i ++ ) {
		if (!sum[i] || sum[i] > i) continue;
		add(i, sum[i]);
		add(sum[i], i);
	}
	ans = 1;
	for (int i = 1; i <= n; i ++ ) {
		dfs(i);
	}
	printf("%d\n", ans);
	return 0;
}