「一本通 5.2 例 3」数字转换

题目描述

给定正整数 $n$ 。若数 $x$ 的真约数和 $y$ 满足 $y < x$ ，则 $x$ 与 $y$ 可以互相变换（双向）。所有变换数字必须在 $1 \sim n$ 范围内。求不断变换且不出现重复数字的最多变换步数。

输入：一个正整数 $n$ 。
输出：最多变换步数。
样例输入：7
样例输出：3（路线 $4 \to 3 \to 1 \to 7$ ）
数据范围： $1 \le n \le 50000$ 。

思路

$s(x) < x$ 时把 $x$ 与 $s(x)$ 连无向边，可证图中无环，形成森林。树上不重复路径即树直径，每棵树两次 BFS 求直径取最大。真约数和用倍数筛 $O(n \log n)$ 预处理。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 19:46
# update_at: 2026-09-30 19:46

import sys


def divisor_sum_table(n: int) -> list[int]:
    """筛法求 1..n 每个数的真约数和（不含自身）。"""
    s = [0] * (n + 1)
    for d in range(1, n // 2 + 1):
        for m in range(d * 2, n + 1, d):  # d 是 m 的真约数，逐个累加
            s[m] += d
    return s


def build_graph(n: int) -> list[list[int]]:
    """建无向图：真约数和 y < x 时连边 x—y，双向可变换。"""
    s = divisor_sum_table(n)
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for x in range(2, n + 1):
        y = s[x]
        if y < x:  # y == x（完全数）或 y > x 时本侧不建边；对侧若满足会由对侧建出
            adj[x].append(y)
            adj[y].append(x)
    return adj


def farthest(adj: list[list[int]], start: int) -> tuple[int, int, list[int]]:
    """从 start 分层扩散，返回 (最远点, 最远距离, 走过的所有点)。"""
    dist: dict[int, int] = {start: 0}
    layer = [start]
    far = start
    depth = 0
    while layer:
        nxt = [v for u in layer for v in adj[u] if v not in dist]
        if not nxt:
            break
        depth += 1
        for v in nxt:
            dist[v] = depth
        far = nxt[-1]  # 最后一层任意一点都可作为"最远点"
        layer = nxt
    return far, depth, list(dist)


def forest_diameter(adj: list[list[int]]) -> int:
    """森林求直径：每块先任取一点找最远点，再从它扩散，距离即该块直径。"""
    seen: set[int] = set()
    ans = 0
    for start in range(1, len(adj)):
        if start in seen:
            continue
        u, _, nodes = farthest(adj, start)   # 第一次：确定连通块一端 u，并标记整块
        seen.update(nodes)
        _, diameter, _ = farthest(adj, u)    # 第二次：u 出发的最远距离就是直径
        ans = max(ans, diameter)
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    print(forest_diameter(build_graph(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:48
 * update_at: 2026-10-06 00:48
 */

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXN = 50005;

int n;
int s[MAXN];           // s[x]：x 的真约数和
vector<int> g[MAXN];   // 无向森林邻接表
int vis[MAXN];         // BFS 访问标记兼距离

// 筛法求 1..n 每个数的真约数和：d 枚举倍数
void calc_divisor_sum() {
    for (int d = 1; d <= n / 2; ++d) {
        for (int m = d * 2; m <= n; m += d) {
            s[m] += d;
        }
    }
}

// 建图：若 s[x] < x 则 x 与 s[x] 连无向边
void build_graph() {
    for (int x = 2; x <= n; ++x) {
        int y = s[x];
        if (y < x) {
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
}

// 从 start 开始 BFS，返回 (最远点, 最远距离)，同时把访问过的点存入 reached
pair<int, int> bfs(int start, vector<int> &reached) {
    queue<int> q;
    q.push(start);
    vis[start] = 0;
    reached.push_back(start);
    int far = start;
    int maxd = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)g[u].size(); ++i) {
            int v = g[u][i];
            if (vis[v] != -1) continue;
            vis[v] = vis[u] + 1;
            q.push(v);
            reached.push_back(v);
            if (vis[v] > maxd) {
                maxd = vis[v];
                far = v;
            }
        }
    }
    return make_pair(far, maxd);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (!(cin >> n)) return 0;

    calc_divisor_sum();
    build_graph();

    // 森林直径：每个连通块两次 BFS
    memset(vis, -1, sizeof(vis));
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[i] != -1) continue;   // 已访问过，属于之前的连通块
        vector<int> nodes;
        pair<int, int> p1 = bfs(i, nodes);   // 第一次：找连通块一端 u，nodes 记录整块
        int u = p1.first;
        // 第二次从 u 出发，只在该连通块内 BFS
        for (int j = 0; j < (int)nodes.size(); ++j) vis[nodes[j]] = -1;
        vector<int> dummy;
        pair<int, int> p2 = bfs(u, dummy);   // 最远距离即该树直径
        ans = max(ans, p2.second);
    }

    cout << ans << "\n";
    return 0;
}

「一本通 5.2 例 3」数字转换

目录

题目描述

思路

参考代码