python - 计算两个列表中的对，当相乘时形成一个完美的平方

Question

这个问题已经有答案了:

Find pairs in two arrays such that when multiplied becomes a perfect square (4 个回答)

已关闭 3 年前。

给你两个列表，你必须找出构成完美正方形的对。

例如:

a = [2, 6, 10, 13, 17, 18]

b = [3, 7, 8, 9, 11, 15]

有两对(2,8)和(8,18) .

有没有比暴力破解更有效的方法呢？这是我的代码，时间复杂度为 O(n*m)(其中n是a的长度，m是b的长度)。

pl = []
a = [ 2, 6, 10, 13, 17,18]
b = [ 3, 7, 8, 9, 11, 15 ]
i = 0
while(i < len(a)):
    j = 0
    while(j < len(b)):
        p = a[i]*b[j]
        n = p**0.5
        u = int(n)
        if n == u:
            pl.append((a[i],b[j]))

        j = j+1


    i = i+1

print(pl)

这个问题在使用C#之前已经被问过here ，但我不明白他们所说的“我们需要为每个数字存储的是它的质因数中有一个奇数”是什么意思，所以我无法在我的Python代码中实现这一点。

有人可以向我解释一下我们如何在 Python 中实现高效的解决方案吗？

Answer 1

链接问题中描述的逻辑如下。完全平方数的质因数总是成对出现。例如，36 =​​ 2*2*3*3。我们有两个 3 和两个 2。因此，如果我们取任意两个数字相乘形成一个完全平方数，如果我们将它们的每个质因子的计数相加，我们也会得到偶数计数。

例如，8 = 2*2*2 和 18 = 2*3*3。合并起来，我们得到四个 2 和两个 3。

下面是一些实现此算法的 Python 代码，使用collections.Counter 并设置来删除重复项。首先，我们预先计算 a 和 b 中每个唯一元素的所有素数分解以避免冗余，并将其存储在字典中。然后，我们使用 itertools.product 循环遍历 a 和 b 中的元素对，并合并素因子计数。如果每个计数都是偶数，我们将已排序的对添加到一个集合中。

代码:

from collections import Counter
import itertools

def prime_factors(n):
    """
    https://stackoverflow.com/a/22808285/12366110
    """
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return Counter(factors)

a = [2, 6, 10, 13, 17,18]

b = [3, 7, 8, 9, 11, 15]

prime_factors = {i: prime_factors(i) for i in set(a) | set(b)}

rv = set()

for a, b in itertools.product(a, b):
    combined_counts = prime_factors[a] + prime_factors[b]
    if all(v%2 == 0 for v in combined_counts.values()):
        rv.add(tuple(sorted([a, b])))

输出:

>>> rv
{(2, 8), (8, 18)}