$$\color{Red}{数字转换 步骤详解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

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

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

输入格式

输入一个正整数 n。

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

数据范围

1 ≤ n ≤ 50000

输入样例：

7

输出样例：

3

样例解释
一种方案为：4→3→1→7

思考

初见大家应该会先意识到我们需要先懂得怎么筛约数

算法基础课中的优化筛法
朴素做法是，O(n^2)的做法，枚举所有从1到n的组合乘积为n的情况。但是复杂度高。
算法基础课中有一个很巧妙的做法：试除法求约数。每个数字n只需要枚举到根号n即可（因为约数总是两两成对，相乘为n），一个变大另一个变小，交界点是两者相等都为根号n

x = Integer.parseInt(br.readLine());
for(int i=1; i<=Math.sqrt(x); i++) {
    if (x % i == 0) cnt ++;
}

但是这个做法还是复杂度太高，我们每个数都需要从头到根号n做一遍相同的操作。同时分析这道题，彼此之间的转化关系，如果我们用图的思想去考虑，应该是一片森林，根节点应该是不可再分的情况，即没有比自己更小的约数和的数。
然后和能转化的更大的数，即自己为它的约数和的情况的节点构成的一颗颗树。

这里y总提供了一个很妙的找约数的方法，相当于默认把i看作一个约数，去枚举i从1到n的所有倍数，这道题因为限制了不能让约数等于自己，所以第二层for循环应该从2开始，相当于一个调和级数，最终复杂度为O(nlog(n))
—>n(1 + 1/2 + 1/3 + """ + 1/n) —> ln(n) + C

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

我们按照上面的思路去构图即可。找寻最长的转化步数等同于我们之前做的树的最长路径这道题完全相同的步骤，这里把题解放在这，就不过多赘述了。

树的最长路径

这里其实有一个很有趣的现象，就是最后不枚举答案，我们直接dfs（1）这道题能过

这里很多大佬都试着去证明了，我这里就不证明了，代码还是循环按st数组，把未遍历的树遍历。。
理性判断，任何数字，可能拆分最后都是质数的乘积，质数的约数除了自己就只有1，可以从反证法的角度看。

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 50010, n, idx, ans;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static boolean[] st = new boolean[N];
    static int[] fsum = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    static int dfs(int x) {
        st[x] = true;
        int d1 = 0, d2 = 0;
        for (int i = h[x]; 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 = Math.max(ans, d1 + d2);
        return d1;
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        Arrays.fill(h, -1);
        //这里我们和之前的筛约数思想一样，为什么只加i是因为约数成对的出现，我们同时加i和j会让约数加两次
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= n / i; j++) {
                fsum[i * j] += i;
            }
        }
        //建立森林
        for (int i = 2; i <= n; i++) {
            if (i > fsum[i])
                add(fsum[i], i);
        }
        for (int i = 1; i <= n; i++) {
            if (!st[i])
                dfs(i);
        }
        System.out.println(ans);
    }
}