Учитывая 2 массива длины n, a и b, я хочу найти такое количество пар, что Gcd (a [i], b [j]) == 1 меньше, чем O (n ^ 2).
РЕДАКТИРОВАТЬ: Посмотрите на это
Если размер чисел в $ O (n) $, вы можете использовать следующий метод, чтобы сделать это в $ O (nlog (n)) $ (от здесь ):
Эффективный подход. Эффективным решением является генерация всех простых множителей целых в данном массиве. Используя ha sh, сохраните счетчик каждого элемента, который является основным фактором любого числа в массиве. Если элемент не содержит общего простого множителя с другими элементами, он всегда образует пару взаимно простых чисел с другими элементами. Для генерации простых множителей, пожалуйста, go через статью Простая факторизация с использованием Sieve in O (log n) .
Вы можете найти реализацию алгоритма на C ++ в этом источнике. а также.
Более того, если вы ограничены для предварительного вычисления, вы можете использовать O(\sqrt(n)) для простого факторинга, и ваш алгоритм будет в O(n\sqrt(n)).
O(\sqrt(n))
O(n\sqrt(n))