c# - 在两个数组中找到对，这样当相乘时变成一个完美的正方形

Question

给定两个像这样的整数数组:-

int[] a = { 2, 6, 10, 13, 17,18 };
int[] b = { 3, 7, 8, 9, 11, 15 };

我如何从这两个数组中找到对，使得它们相乘时成为完美的正方形？

例如，在上面的数组中，{2,8} 和 {18,8} 是两对。

现在我的方法是蛮力，我像这样遍历两个数组:-

int count = 0;
for (int i = 0; i < arr1.Length; i++)
{
    for (int j = 0; j < arr2.Length; j++)
    {
         var x = arr1[i] * arr2[j];
         long s = (long)Math.Sqrt(x);
         if (x == s * s)
               count += 1;                   
     }
}

我怎样才能有效地做到这一点？

Answer 1

任何两个数字中每个质因数的计数都是偶数，将形成一个有效的对。否则，任何具有一个或多个质因数的奇数个数只能与另一个具有奇数个完全相同因数的数配对。这意味着我们需要为每个数字存储的是它的哪些质因数具有奇数。这可以被散列。

a = { 2, 6, 10, 13, 17,18 }; 
b = { 3, 7, 8, 9, 11, 15 };

散列较短的数组，其中键是素数与奇数的组合，值是数组中对应的索引列表:

a = {
  2: [0,5],
  2-3: [1], 
  2-5: [2], 
  13: [3],
  17: [4]
}

遍历第二个数组，精确匹配prime-factor-with-odd-count-combination:

b[0] -> 3, no match
b[1] -> 7, no match
b[2] -> 2, match with a[0] and a[5] -> 2 * 8 and 18 * 8 are perfect squares
b[3] -> None, no match
b[4] -> 11, no match
b[5] -> 3-5, no match