将两个给定范围内的两个随机整数相乘得到n的概率

Question

这就是挑战：给我四个数字：a,b,c,d。然后给出了数字n，它描述了要检查的数字数量。然后输入这些数字，目标是找出如果将两个随机数相乘（一个来自a to b范围，另一个来自c to d范围）得到该数字的概率。最后，我需要以“p/q”格式输出该概率。我找到了解决方案，但问题是当处理更大的数字时，它会占用太多时间。我还有另一个解决方案，首先创建一个包含所有可能组合的列表，但在这种情况下，它会占用太多内存

from math import gcd

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

def findProb(z):
    repeats = 0
    nec_mulps = [z//x for x in range(a,b+1) if z%x == 0]
    for n in nec_mulps:
        if n in range(c,d+1):
            repeats+=1
    probGCD = gcd(repeats,combs_quantity)
    return str(repeats//probGCD) + "/" + str(combs_quantity//probGCD)

probability = []
n = int(input())
for i in range(n):
    probability.append(findProb(int(input())))
for p in probability:
    print(p)

Answer 1

@MBo在上面说，复杂性是sqrt(z)。您可以将repeats计算为：

    divisors = []
    i = 1
    while i * i <= z:
        if z % i == 0:
            divisors.append(i)
            if i * i < z:
                divisors.append(z // i)
        i += 1
    repeats = 0
    for divisor in divisors:
        if a <= divisor <= b and c <= z // divisor <= d:
            repeats += 1

Answer 2

获取n的所有除数

对于属于范围a..b的每个除数Z，检查互补除数n//Z是否位于范围c..d