从两个列表中计算对，当它们相乘时形成一个完美的正方形

Question

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

例如：

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# 之前有人问过这个问题，但我不明白 "All we would need to store for each number is which of its prime factors have an odd count" 的意思，所以我无法在我的 Python 代码中实现它.

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

Answer 1

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

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

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

代码：

from collections import Counter
import itertools

def prime_factors(n):
    """
    
    """
    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)}

从两个列表中计算对，当它们相乘时形成一个完美的正方形

Compute pairs from two lists that when multiplied make a perfect square

python

python-3.x

list

math

perfect-square