Python实现getTotalX函数报runtime error无stdout输出求助

给定两个整数数组，需统计同时满足以下两个条件的整数总个数：

• 第一个数组的所有元素均为待判定整数的因数
• 待判定整数为第二个数组所有元素的因数
  满足上述条件的数被称为处于两个数组之间的数，需计算这类数的总数量。

题目示例 #

• 第一个数组 a = [2,6]
• 第二个数组 b = [24,36]
  符合条件的数共有2个：6和12，验证规则如下：

1. 对第一个数组的整除验证：6%2=0、6%6=0、12%2=0、12%6=0
2. 对第二个数组的整除验证：24%6=0、36%6=0、24%12=0、36%12=0

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'getTotalX' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY a
#  2. INTEGER_ARRAY b
#

def getTotalX(a, b,k,count):
   flag = 0
   p=count
   l = max(b)
   if(k<=l):
    for i in range(len(a)):
        if(k%a[i]!=0):
                flag=1
        for j in range(len(b)):
            if(b[j]%k!=0):
                flag=1
        if(flag==0):
            count+=1
            getTotalX(a,b,k+1,count)
        else:
            getTotalX(a,b,k+1,count)
    else:
          
        return p
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    arr = list(map(int, input().rstrip().split()))

    brr = list(map(int, input().rstrip().split()))

    total = getTotalX(arr, brr,max(arr),0)

    fptr.write(str(total) + '\n')

    fptr.close()

运行上述代码时触发runtime error，标准输出无响应，报错截图如下：

代码存在4个核心问题，直接导致运行报错和逻辑错误：

1. 递归深度溢出：使用递归实现从max(a)到max(b)的数值遍历，Python默认递归深度上限约为1000，当第二个数组的最大值超过1000时会直接触发栈溢出的runtime error，这是报错的核心原因。
2. 返回值逻辑缺失：递归分支中调用getTotalX时没有接收和传递返回值，仅在递归终止分支返回变量p，最终主函数拿到的返回值为None，无法得到正确计数结果。
3. 循环嵌套逻辑错误：将遍历第二个数组b的校验逻辑写在了遍历第一个数组a的循环内部，每检查a中一个元素就会重复遍历整个b数组，既做了冗余计算，也会导致flag标记逻辑混乱。
4. 函数参数定义冗余：原函数定义需要传入k、count两个遍历状态参数，但主流程调用时不需要额外传这两个参数，不符合题目给出的函数入参要求。

弃用容易溢出的递归实现，改用普通循环实现遍历校验，修正循环嵌套逻辑，去掉冗余参数，修复后可正常运行的代码如下：

#!/bin/python3
import math
import os
import sys

def getTotalX(a, b):
    count = 0
    range_start = max(a)
    range_end = max(b)
    # 遍历所有可能的候选数
    for candidate in range(range_start, range_end + 1):
        is_valid = True
        # 校验：a中所有元素都是候选数的因数
        for num in a:
            if candidate % num != 0:
                is_valid = False
                break
        if not is_valid:
            continue
        # 校验：候选数是b中所有元素的因数
        for num in b:
            if num % candidate != 0:
                is_valid = False
                break
        if is_valid:
            count += 1
    return count

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    first_multiple_input = input().rstrip().split()
    n = int(first_multiple_input[0])
    m = int(first_multiple_input[1])
    arr = list(map(int, input().rstrip().split()))
    brr = list(map(int, input().rstrip().split()))
    total = getTotalX(arr, brr)
    fptr.write(str(total) + '\n')
    fptr.close()

性能优化思路 #

如果数组元素取值范围很大，可以通过数学方法减少遍历次数：

1. 先计算第一个数组a所有元素的最小公倍数（LCM），所有符合条件的数一定是这个LCM的倍数
2. 再计算第二个数组b所有元素的最大公约数（GCD），所有符合条件的数一定是这个GCD的因数
3. 只需要遍历从LCM到GCD之间、是LCM倍数的数做校验即可，遍历次数会大幅降低。

内容的提问来源于stack exchange，提问作者Konduru Premsai