python - 来自 2 个范围的 2 个元素的总和将是一个给定的数字

Question

我需要做一个快速算法(我已经做了一个慢的算法)，它将从两个整数范围(范围可以相交或不相交)中找到所有可能值的数量，其总和将是给定的数字

我可以用等式表示它:z = x + y
其中 z 是一个已知数，等于 x 加上 y
z 可以是 0 到 10^18 之间的任意数字

x 属于整数范围 [a..b]，其中 0 <= a <= b <= 10^18 和
连续数相差1

y 属于整数范围 [c..d]，其中 0 <= c <= d <= 10^18 和
连续数相差1

所以我需要从两组数字中找到 x 和 y 的所有可能变化的数量(不是它们的确切值)，总和将为 z

例子:
z = 5
第一组:a = 1, b = 5(表示该组由1,2,3,4,5组成)
第二组:c = 1, b = 5
那么答案就是4，因为所有可能的组合都是:
x = 4, y = 1
x = 3, y = 2
x = 2, y = 3
x = 1, y = 4
因为他们的总和是 5 的

算法的强制条件是运行速度快于 1 秒

下面的代码工作正常，但只适用于小于 1000000 的数字。对于大数字，它开始工作得更慢

with open(r"input.txt") as f:
    n = int(f.readline()) # the given number
    a = int(f.readline()) # the start position of the first set
    b = int(f.readline()) # the end position of the first set
    c = int(f.readline()) # the start position of the second set
    d = int(f.readline()) # the end position of the second set
   # print "n:",n,"a:",a,"b:",b,"c:",c,"d:",d

t = b - a + 1 # all posible variants of the first set
k = d - c + 1 # all posible variants of the second set
number_of_vars = 0 

if t >= k:
    while b >= a:
        if (n - b <= d) \
                and (n - b>= c):
            number_of_vars += 1
            b -= 1
        else:
            b -= 1

if t < k:
    while d >= c:
        if (n-d <= b) and (n-d >= a):
            number_of_vars += 1
            d -= 1
        else:
            d -= 1

print number_of_vars

Answer 1

不需要算法——只需代数:

统计x的个数就够了在[a,b]为此 z - x在[c,d]

两者都需要 a <= x <= b和 c <= z - x <= d .第二个不等式相当于z - d <= x <= z - c因此你需要

max(a, z - d) <= x <= min(b,z - c)

这样的数量x是0如果min(b,z - c) < max(a, z - d)否则就是

min(b,z - c) - max(a, z - d) + 1

无论哪种情况，解决方案的数量都是

max(0, min(b,z - c) - max(a, z - d) + 1)

在你的例子中 a = c = 1和 b = d = z = 5和

min(b, z - c) - max(a, z - d) + 1 = min(5,4) - max(1,0) + 1 = 4 - 1 + 1 = 4