数字转换

树形dp 树直径

题目描述

#10155. 「一本通 5.2 例 3」数字转换 - 题目 - LibreOJ (loj.ac) 如果一个数 x 的约数（不包括他本身）的和 y 比他本身小，那么 x 可以变成 y ， y 也可以变成 x 。例如 4 可以变为 3 ， 1 可以变为 7 。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数 n 。

输出格式

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

样例

input

7

output

3

一种方案为 $4\to 3\to 1\to 7$。

数据范围

对于 $100\%$ 的数据，$1\le n\le 50000$。

思路

对于数字6, 它的约数为 1 2 3, 总和为6, 无法变换。 对于数字4, 它的约数为 1 2, 总和为3, 故可以 4 变换 3。

显然对于每个数字, 能变换过去的约数只有一个, 因此可以看做只有一个父节点。问题可以转化为图论树模型： 所以我们要求的就是该树的最长路径（直径）。 按照该模板题的方法求即可。树的最长路径 求一个数的所有约数可以使用试除法试除法(sqrt(n))。注意减去该数本身。 总算法复杂度为 $O(n\sqrt{n})$ 求约数还可以用标记法, 即求该数是那些数的约数, 类似于埃氏筛 这种的复杂度是调和级数$n+\frac{n}{2}+\frac{n}{3}..$, 复杂度为$O(logn)$

代码

const int N = 5e4 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int n;
int ans;
int sum[N]; // i数的约数之和
 
// 试除法
int get(int i)
{
    int res = 0;
    for (int j = 1; j <= i / j; j++)
        if (i % j == 0)
        {
            res += j;
            if (j != i / j)
                res += i / j;
        }
    res -= i;
    return res;
}
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
int dfs(int u, int fa)
{
    int dist = 0;
    int d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
 
        int d = dfs(j, u) + 1;
        dist = max(dist, d);
        if (d >= d1)
            d2 = d1, d1 = d;
        else if (d > d2)
            d2 = d;
    }
    ans = max(ans, d1 + d2);
    return dist;
}
 
int main()
{
    FasterIO;
    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 = 1; i <= n; i++)
    {
        int b = sum[i];
        if (i > b)
            add(i, b), add(b, i);
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}