AcWing1075. 数字转换

题目描述

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

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

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

解题思路

\(\qquad\)我们将这道题转化成图论模型，将符合题目描述中的 \(x,y\) 连接一条 \(y\to x\) 的有向边，最后我们的图会显示出一个森林的样子
\(\qquad\)然后原问题抽象为求树的直径，我们只需要把森林里所有树的直径求出来然后取最值即可
对于约数和这一条件，正难则反，我们可以枚举约数，然后再枚举倍数，用 \(sum[x]\) 表示 \(x\) 的约数和，用当前枚举数 \(i\) 乘上倍数 \(j\)，也就是 \(sum[i\times j] += i\) 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;
int h[N], e[N], ne[N], idx;
int st[N], d[N], res;
int n, sum[N];

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

void build() 
{
    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 (i > sum[i]) add(sum[i], i);
}

void dp(int x) 
{
    st[x] = 1;
    for (int i = h[x]; ~i; i = ne[i]) 
    {
        int y = e[i];
        if (st[y]) continue ;
        dp(y);
        res = max(res, d[x] + d[y] + 1);
        d[x] = max(d[x], d[y] + 1);
    }
    res = max(res, d[x]);
}

int main() 
{
    scanf("%d", &n);
    
    build();
    
    for (int i = 1; i <= n; i ++ ) 
        if (!st[i]) dp(i);
    printf("%d\n", res);
    
    return 0;
}