algorithm - 统计三元组 a*b=c 的个数

Question

问题是计算三元组的数量

a * b = c
where a1 <= a <= a2 and b1 <= b <= b2 and c1 <= c <= c2

输入将是 a1,a2,b1,b2,c1,c2

我能想到的解决方案是使用两个嵌套循环，从 a1 迭代到 a2，第二个循环从 b1 迭代到 b2，然后将它们中的每一个相乘，看看相乘后的值是否在 c1 到 c2 的范围内，然后递增计数.

当约束非常高时如何有效解决问题，即所有 a1,a2,b1,b2,c1,c2 的值都在 0 到 1000000000 之间。

Answer 1

第 1 部分:复杂度为 O(a2 - a1) 的解决方案。

首先，请注意给定一个 a , 我们可以很容易地计算出 b 的数量b1 <= b <= b2 的值, 也满足 c1 <= a * b <= c2 .后一个条件相当于 c1 / a <= b <= c2 / a , 因此我们需要统计满足 max(b1, c1/a) <= b <= min(b2, c2/a) 的整数 b 的个数.

这个号码是N(a) = floor(min(b2, c2/a)) - ceil(max(b1, c1/a)) + 1 -- 关系 (1) .

问题的解决方案是N(a1) + N(a1 + 1) + ... + N(a2) .

这比遍历所有 (a, b) 更有效对并检查他们的产品，但是，对于给定的输入量级，它可能仍然不够快——复杂度为 O(a2 - a1) .由于问题在 a 中是对称的和 b , 使用 O(b2 - b1) 可能更有利复杂性。

在接下来的两部分中，我将描述一个更高效的解决方案。

---

第 2 部分:将问题简化为更简单的问题。

让我们表示为 N(a1, a2, b1, b2, c1, c2)我们需要计算的值。

请注意，我们可以将问题简化为 c1 = 0 的两个问题，使用:

N(a1, a2, b1, b2, c1, c2) = N(a1, a2, b1, b2, 0, c2) - N(a1, a2, b1, b2, 0, c1 - 1) .

我们可以更进一步，将 c1 = 0 的问题简化为 b1 = 0 和 c1 = 0 的两个问题。这可以使用:

N(a1, a2, b1, b2, 0, C) = N(a1, a2, 0, b2, 0, C) - N(a1, a2, 0, b1 - 1, 0, C) .

类似地，我们可以将 b1 = 0 和 c1 = 0 的问题简化为 a1 = 0, b1 = 0, c1 = 0 的两个问题。

因此，足以解决需要计算以下形式的值的更简单的问题:N(0, A, 0, B, 0, C) ，即我们需要计算自然数三元组的数量 (a, b, c) , 与 c = a * b , a <= A , b <= B , c <= C .

---

第 3 部分:复杂度为 O(sqrt(c2)) 的解决方案。

下一个有用的观察是自 a * b = c <= C ，至少以下关系之一为真:a <= sqrt(C) , 或 b <= sqrt(C) -- 观察 (2) .

在证明的第一部分(关系 1 )表明我们可以有效地计算(在 O(1) 中)好的 b 的数量。值如果 a是固定的。使用该关系，我们可以有效地计算 a <= sqrt(C) 的三元组数量。 -- 在 O(sqrt(C)) .

剩下要做的就是用a > sqrt(C)计算三胞胎的数量。 .据观察(2) ，我们知道在这种情况下需要有 b <= sqrt(C) .

因此，对于任何 b在 {0, 1, 2, ..., sqrt(C)}我们要数好人数a值使得 sqrt(C) < a < A .我们可以再次应用关系 (1) (这次 a 和 b 的角色相反——我们现在给出 b 并计算好的 a 值的数量，它受属于某个区间的约束)。对于每个 b在 {0, 1, 2, ..., sqrt(C)} ，我们可以数一数好的a在 O(1) -- 因此这种情况的复杂性又是O(sqrt(C)) .

使用以上结果，我们得到整体复杂度 O(sqrt(C)) .回到最初的问题，这涉及一个 O(sqrt(c2))复杂性。