查找两个数组中的对，使得相乘时成为一个完美的平方 [英] Find pairs in two arrays such that when multiplied becomes a perfect square

问题描述

给出两个整数数组，如下所示：-

Given two integer arrays like this:-

int [] a = {2，6，10，13，17,18 };

int [] b = {3、7、8、9、11、15};

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

我怎么能从这两个数组中找到对，使得它们相乘时变成完美的正方形？

How can I find pairs from these two arrays such that when multiplied they become perfect square?

例如，在上述数组中， {2,8} & {18,8} 是两对。

For eg, in above arrays {2,8} & {18,8} are two pairs.

现在我的方法是蛮力，我在其中循环通过这样的两个数组：-

Right now my approach is brute-force, where I am looping through both arrays like this:-

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;                   
     }
}

如何有效地做到这一点？

How can I do this efficiently?

推荐答案

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

Any two numbers where the count of each prime factor in the number is even, would form a valid pair. Otherwise, any number with an odd count of one or more prime factors could only pair with another number with the exact same factors having an odd count. This means all we would need to store for each number is which of its prime factors have an odd count. This could be hashed.

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

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

Hash the shorter array where the key is the combination of prime factors with odd count and the value is the corresponding list of indexes in the array:

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

遍历第二个数组并与奇数组合的素数完全匹配：

Traverse the second array and exactly match the 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

这篇关于查找两个数组中的对，使得相乘时成为一个完美的平方的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！