Найти пары в двух массивах так, чтобы при умножении получился идеальный квадрат

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

Пройдите по второму массиву и точно сопоставьте комбинацию простого фактора с нечетным числом:

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

Answer 2

Для упорядоченных (имеет значение только для определения max) массивов с целыми числами> 0 с помощью модифицированного сита Эратосфена, я думаю, сложность составляет O(max * log(max) * log(log(max)) + n) и требуется дополнительное пространство O(max) (которое может быть огромным улучшением или очень плохим в зависимости от n и max по сравнению со стандартным O(n^2) с пространством O(1) и без зависимости от max):

long total = 0;
int max = (a[a.length - 1] > b[b.length - 1] ? a[a.length - 1] : b[b.length - 1]) + 1;
int[] sieve = new int[max], anti = new int[max], count = new int[max];
for (int i = 1; i < max; i++) {
    sieve[i] = i; // using numbers and divide by prime instead of booleans
    anti[i] = 1; // number by which i has to be multiplied to get the smallest square
}
for (int i = 2; i < max; i++) {
    if (sieve[i] == i) { // i is prime
        for (int j = i; j < max; j += i) {
            boolean odd = false;
            do {
                odd = !odd;
                sieve[j] /= i;
            } while (sieve[j] % i == 0);
            if (odd)
                anti[j] *= i;
        }
    } // if you know the max over all the calls the above has only to be done once
} // except for resetting count and total, so we would get O(n) because max is constant
for (int i = 0; i < a.length; i++)
    count[anti[a[i]]]++; // hash map for count is better than array if n < max
for (int i = 0; i < b.length; i++)
    total += count[anti[b[i]]];

Квадратное число будет отображаться в 1, а другие в произведение простых чисел с нечетными показателями в факторизации числа. В вашем примере каждое число сопоставляется с самим собой, кроме 8 => 2, 9 => 1, 18 => 2. Другие интересные числа ниже 18 (не квадратные или не сопоставляемые с самим собой): 12 => 3. При итерации по Алгоритм увеличивает число 2 один раз при посещении 2 и один раз при посещении 18. Общая сумма будет увеличена на 2, когда итерация по b посещает 8, единственное совпадение между двумя массивами и, следовательно, конечный результат.

Answer 3

Мне удалось упростить это с помощью LINQ:

int[] arr1 = { 2, 6, 10, 13, 17, 18 };
int[] arr2 = { 3, 7, 8, 9, 11, 15 };
int count = arr1.Sum(t => (from t1 in arr2 select t*t1 into x let s = (long) Math.Sqrt(x) where x == s*s select x).Count());

Answer 4

Я бы проверил, есть ли у вас десятичное место после рисования корня слева. Если нет, то у вас есть идеальный квадратный корень:

void Main()
{
    int[] arr1 = { 2, 6, 10, 13, 17, 18 };
    int[] arr2 = { 3, 7, 8, 9, 11, 15 };

    List<string> PairList = new List<string>();

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < arr2.Length; j++)
        {
            if (Math.Sqrt(arr1[i] * arr2[j]) % 1 == 0)
            {
                PairList.Add(String.Format("{0} & {1}", arr1[i] , arr2[j]));
            }           
        }
    }

    PairList.Dump();
}