从两个给定整数区间随机取数相乘得到指定数的概率计算性能优化技术问询

嘿，我来帮你搞定这个计算概率时的性能问题！先看看现有代码的核心问题：

• 你的findProb函数每次都要遍历整个[a,b]区间来找能整除目标数z的数，要是a和b的跨度很大（比如从1到1e6），这遍历起来慢得要死，尤其是待检查的数字多的时候，整体效率直接拉胯。
• 预先生成所有数对的方案更不靠谱，区间一大内存直接爆掉，完全不现实。

优化思路 #

咱们换个角度想：不用遍历整个区间找因数，直接找出z的所有因数，再筛选符合区间条件的因数对。这样能把时间复杂度从O(b-a)降到O(√z)，速度提升一大截，还完全不会有内存占用过高的问题。

另外还要补个原代码的小bug：当z=0且[a,b]里包含0时，z%x会触发除以0的错误，得单独处理这种情况。

优化后的代码 #

from math import gcd, isqrt

a, b, c, d = map(int, input().split())
total_pairs = (b - a + 1) * (d - c + 1)

def count_valid_pairs(z):
    # 单独处理z=0的情况，避免除以0错误
    if z == 0:
        # 计算x=0且y≠0的数量 + x≠0且y=0的数量
        # 统计[a,b]中0的个数
        count_x0 = max(0, min(b, 0) - max(a, 0) + 1) if a <= 0 <= b else 0
        # 统计[c,d]中0的个数
        count_y0 = max(0, min(d, 0) - max(c, 0) + 1) if c <= 0 <= d else 0
        non_zero_x = (b - a + 1) - count_x0
        non_zero_y = (d - c + 1) - count_y0
        return count_x0 * non_zero_y + non_zero_x * count_y0
    
    count = 0
    # 高效找出z的所有因数
    factors = set()
    sqrt_z = isqrt(z)
    for i in range(1, sqrt_z + 1):
        if z % i == 0:
            factors.add(i)
            factors.add(z // i)
    
    # 筛选符合条件的(x, y)对：x在[a,b]，y=z/x在[c,d]
    for x in factors:
        if a <= x <= b:
            y = z // x
            if c <= y <= d:
                count += 1
    return count

def findProb(z):
    valid_count = count_valid_pairs(z)
    common_div = gcd(valid_count, total_pairs)
    return f"{valid_count//common_div}/{total_pairs//common_div}"

n = int(input())
results = []
for _ in range(n):
    z = int(input())
    results.append(findProb(z))

for res in results:
    print(res)

优化点说明 #

1. 特殊情况兜底：专门处理z=0的场景，计算所有能得到0的数对组合，再也不会触发除以0的错误了。
2. 快速找因数：只遍历到√z就能找出所有因数，比遍历整个[a,b]效率提升几个量级——比如原区间跨度1e9时，原代码要跑1e9次，现在只需要跑3e4次（因为√1e9是31622左右）。
3. 精准筛选：从所有因数里挑出符合区间条件的x，再检查对应的y是否符合要求，统计数量精准又高效。
4. 分数化简不变：还是用gcd来化简分数，保证输出的是最简分数格式。

这个方案既解决了原代码的性能问题，又避开了预生成数对的内存坑，还修了潜在bug，完美！

内容的提问来源于stack exchange，提问作者Vitalyk Chernysh