提取数字串中Pronic整数并优化代码超时问题

问题描述 #

给定超大整数N（1 ≤ N ≤ 10^20），需提取其中所有由连续数字组成的Pronic整数（可表示为n*(n+1)的形式，n为非负整数），并按其在N中的出现顺序输出。原有代码处理长度大于10的字符串时超时，需优化以满足4000毫秒的时间限制。

原有代码的问题 #

1. 判断逻辑低效：ispro函数通过暴力遍历从0到n来验证是否为Pronic数，当n为10^{20级时，循环次数达到10}20次，完全无法在时限内完成。
2. 子串遍历冗余：pro函数的双重循环生成大量无效子串（如i>j的空串），且每次都重复进行字符串-整数-字符串的转换，额外消耗性能。

优化方案 #

核心思路 #

1. 用二分法快速判断Pronic数：利用n*(n+1)的单调递增特性，通过二分查找在O(logx)时间内验证一个数是否为Pronic数，替代暴力遍历。
2. 高效遍历有效子串：仅生成符合整数规范的子串（过滤掉长度>1且带前导零的子串），减少不必要的计算。

优化后代码 #

def is_pronic(x):
    if x < 0:
        return False
    left = 0
    right = int(x**0.5) + 1
    while left <= right:
        mid = (left + right) // 2
        product = mid * (mid + 1)
        if product == x:
            return True
        elif product < x:
            left = mid + 1
        else:
            right = mid - 1
    return False

s = input().strip()
result = []
n_len = len(s)
for i in range(n_len):
    # 遍历所有以i为起点的子串，长度从1到剩余长度
    for l in range(1, n_len - i + 1):
        sub = s[i:i+l]
        # 过滤带前导零的非单字符子串
        if l > 1 and sub[0] == '0':
            continue
        num = int(sub)
        if is_pronic(num):
            result.append(sub)
print(' '.join(result))

代码说明 #

1. is_pronic函数：
   • 针对输入整数x，通过二分查找在[0, sqrt(x)+1]范围内寻找n，验证n*(n+1)是否等于x。
   • 时间复杂度为O(logx)，x最大为10^20时，仅需约60次循环即可完成判断。
2. 子串处理：
   • 遍历字符串的每个起始位置i，再遍历所有可能的子串长度l，生成有效子串。
   • 提前过滤长度>1且以0开头的子串，避免无效的整数转换和判断。
3. 结果收集与输出：将符合条件的子串按出现顺序存入列表，最后用空格连接输出。

示例验证 #

• 示例1输入：93042861 → 输出：930 30 0 42 2 6
• 示例2输入：247025123524 → 输出：2 702 0 2 12 2 2352 2

内容的提问来源于stack exchange，提问作者Saran Kumar