AcWing 1075. 数字转换

如果一个数 x的约数之和 y（不包括他本身）比他本身小，那么 x可以变成 y，y也可以变成 x

例如，4可以变为 3，1可以变为 7。

限定所有数字变换在不超过n的正整数范围内进行，
求不断进行数字变换且不出现重复数字的最多变换步数。

7

3

#include<bits/stdc++.h>

using namespace std;

const int N = 50010;

int n;
int sum[N];
int h[N],e[N],ne[N],idx;
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int d1=0,d2=0;
    for(int i=h[u];~i;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); //更新最大值

    return d1;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
            sum[i*j]+=i;

    memset(h,-1,sizeof h);

    for(int i=2;i<=n;i++)
        if(sum[i]<i)
            add(sum[i],i); // i 的约数之和向 i 连一条边

    dfs(1);

    cout<<ans<<endl;

    return 0;
}