Beautiful Numbers问题求解：解决Python实现大数字美丽数判断超时问题

问题根因 #

你写的代码超时核心问题是遍历逻辑效率太低：

• 遍历范围是8 ~ n/2，时间复杂度随n线性增长，n超过10万的时候就会出现明显卡顿
• 每个遍历到的数字都要转字符串做正则校验，额外增加了大量不必要的开销

优化思路 #

反过来先生成所有小于等于n、仅由8和9组成的cute数，再逐个判断这些cute数能不能整除n即可。
cute数的数量非常少：长度为k的cute数只有2^k个，哪怕n是10位数，总候选数也才2046个，遍历成本可以忽略。

优化后代码 #

from collections import deque

n = int(input())
cute_nums = deque([8, 9])
found = False

while cute_nums:
    current = cute_nums.popleft()
    if current > n:
        continue
    if n % current == 0:
        found = True
        break
    # 生成更长的cute数：后面拼接8和9
    cute_nums.append(current * 10 + 8)
    cute_nums.append(current * 10 + 9)

print("beautiful" if found else -1)

方案说明 #

• 用广度优先搜索生成所有符合要求的cute数，不需要正则校验，生成效率极高
• 只要找到任意一个能整除n的cute数就直接终止，不需要遍历完所有候选
• 哪怕n到10^18量级，也能在毫秒级返回结果，完全不会触发超时

内容的提问来源于stack exchange，提问作者Vinay Edula