Python幸运数代码提交在线判题系统显示错误答案求助

阿华AIGC实验室

2026-5-14

解决幸运数判断的问题：逻辑错误、递归溢出与多测试用例处理

首先，我来帮你分析一下你遇到的问题，然后给出正确的解决方案：

你代码的核心问题

1. 逻辑错误：误解幸运数的筛选规则

你的两段代码都用了m = m - m//n或者类似的逻辑，这完全不符合幸运数的生成规则。幸运数的筛选是基于序列位置的筛法，而非对原始数值进行除法和减法操作。

举个例子，9是幸运数，但用你的第一段代码判断：

初始m=9，n=2：9%2≠0，m=9-4=5，n=3
m=5，n=3：5%3≠0，m=5-1=4，n=4
m=4，n=4：4%4==0 → 返回0（错误，9是幸运数）

这说明你的逻辑完全偏离了幸运数的定义。

2. 递归深度溢出（第二段代码）

当输入较大数值（如30886）时，你的递归函数会调用数千次，超过Python默认的递归深度限制（默认是1000），导致栈溢出，程序崩溃，所以没有输出。

3. 未处理多测试用例

在线判题系统通常会输入多个测试用例（每行一个数），但你的两段代码都只读取了一次输入，只能处理第一个测试用例，后续的输入会被忽略，这也是系统提示“Possibly your code doesn't work correctly for multiple test-cases”的原因。

正确的解决方案

方法1：直观的迭代筛法（适合中等输入）

这个方法模拟幸运数的生成过程，容易理解，对于30886这样的输入完全高效：

def is_lucky(n):
    if n < 1:
        return False
    # 初始化从1到n的序列
    lucky_list = list(range(1, n + 1))
    index = 1
    while index < len(lucky_list):
        step = lucky_list[index]
        # 从step-1索引开始，每隔step个元素删除一个（索引从0开始）
        del lucky_list[step-1::step]
        index += 1
    return n in lucky_list

# 处理多测试用例：读取所有输入行
import sys
for line in sys.stdin:
    num = int(line.strip())
    print(1 if is_lucky(num) else 0)

方法2：高效的位置跟踪法（适合超大输入）

如果输入非常大（如1e6以上），上面的方法可能占用较多内存，这时可以用位置跟踪法，不需要生成整个序列，只跟踪目标数在每一轮筛选后的位置：

def is_lucky(x):
    if x < 1:
        return False
    if x == 1:
        return True
    if x % 2 == 0:
        return False
    
    # 第一步筛选后，目标数的位置（奇数的位置为 (x+1)//2）
    target_pos = (x + 1) // 2
    # 初始步长是3（第二步筛选的步长），它在第一步后的位置是2
    step = 3
    step_pos = 2
    
    while step <= target_pos:
        if target_pos % step == 0:
            return False
        # 更新目标数在筛选后的位置
        target_pos -= target_pos // step
        # 更新当前步长在筛选后的位置（步长本身是幸运数，不会被删除）
        step_pos -= step_pos // step
        # 计算下一个步长：下一个步长是当前序列中的第(step_pos+1)个元素对应的原始数值
        # 第一步后的序列是奇数，数值=2*pos-1，经过筛选后位置变为step_pos+1
        next_step_pos = step_pos + 1
        # 反向计算下一个步长的原始数值：需要模拟它在之前所有筛选中的位置
        temp_pos = next_step_pos
        temp_step = 2
        # 回溯第一步筛选
        temp_num = 2 * temp_pos - 1
        # 回溯第二步及以后的筛选
        prev_step = 3
        while prev_step < step:
            if temp_pos % prev_step == 0:
                # 这个数会被删除，不是幸运数，跳过
                next_step_pos += 1
                temp_pos = next_step_pos
                temp_num = 2 * temp_pos - 1
                prev_step = 3
                continue
            temp_pos -= temp_pos // prev_step
            prev_step += 1
        step = temp_num
        step_pos = next_step_pos
    
    return True

# 处理多测试用例
import sys
for line in sys.stdin:
    num = int(line.strip())
    print(1 if is_lucky(num) else 0)