$\LARGE\color{orange}{刷题日记(算法提高课)}$

对于一个数 $x$ 而言，其约数和 $y$ 是固定的，但反过来一个 $y$ 却可以有多个 $x$ 与其对应

因此如果在考虑建图的时候，我们应当是建立从 $y$ 指向 $x$ 的有向边

本题要求最长的转换步数，因此相当于是求一个有向图中的最长路径，直接用 AcWing 1072. 树的最长路径 来做就行，有一点区别的是，树的最长路径是无向图，本题是有相图，也就是不需要 father 这个变量（这个的存在就是为了防止往回走导致死循环）

剩下的问题就是关于如何建图了

在这里，我们需要求出 $2\sim n$ 中每个数的约数和（不能包括 1 ），直接用试除法来做的话复杂度为 $O(n\sqrt{n})$，这里我们采用筛法来做

我们遍历 $1\sim n$ 中的每个数 $i$ ，考虑它们是哪些数的约数（设为 $x$），这样便得到了 $x$ 的约数，再将所有的 $x$ 的约数加起来即可

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5e4 + 10;
int h[N], e[N], ne[N], idx;
int sum[N];
bool st[N];
int n, ans;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u)//有向边，不需要father
{
    int d1 = 0,  d2 = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        int d = dfs(j) + 1;
        if(d >= d1) d2 = d1, d1 = d;
        else if(d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2);//用经过这个点的最长路径来更新ans
    return d1;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
        for(int j = 2; j <= n / i; j++)
            sum[j * i] += i;
    for(int i = 2; i <= n; i++)//这里不能从1开始，因为1的sum[i]为0，而0不能作为约数存在
        if(sum[i] < i)//这个判断一定要有
        {
            add(sum[i], i);//从约数和指向原数的一条有向边，因为一个数的约数和只有一个，反过来却可以有很多个
            st[i] = true;
        }
    for(int i = 1; i <= n; i++)//这里必须从1开始枚举，因为1可以作为任意数的约数
        if(!st[i])
            dfs(i);
    cout << ans << endl;
    return 0;
}