本文共 1266 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要构建一个树结构，其中每个数 x 都与其约数之和 sum[x] 相连（前提是 sum[x] < x）。然后，我们需要找到这个树中最长路径的长度。

方法思路

解决代码

import sysfrom collections import dequedef main():    sys.setrecursionlimit(1 << 25)    n = int(sys.stdin.readline())    sum_num = [0] * (n + 1)    for i in range(1, n + 1):        for j in range(2, n // i + 1):            sum_num[i * j] += i    adj = [[] for _ in range(n + 1)]    for x in range(1, n + 1):        s = sum_num[x]        if s < x and s <= n:            adj[x].append(s)            adj[s].append(x)    visited = [False] * (n + 1)    max_path = 0    q = deque()    q.append((1, 0))    visited[1] = True    while q:        u, d = q.popleft()        if d > max_path:            max_path = d        for v in adj[u]:            if not visited[v]:                visited[v] = True                q.append((v, d + 1))    print(max_path)if __name__ == "__main__":    main()

代码解释

这种方法高效地处理了约数之和的计算，并通过 BFS 确保找到最长路径。代码能够在较大的 n 值下高效运行，满足题目要求。

转载地址：http://epor.baihongyu.com/