У нас есть некоторые неотрицательные числа. Мы хотим найти пару с максимальным gcd. на самом деле этот максимум важнее пары! Например, если у нас есть:
2 4 5 15
НОД (2,4) = 2
НОД (2,5) = 1
НОД (2,15) = 1
НОД (4,5) = 1
НОД (4,15) = 1
НОД (5,15) = 5
Ответ: 5.
Существует решение, которое принимает O (n):
Пусть наши числа a_i. Сначала вычислите m=a_0*a_1*a_2*.... Для каждого числа a_i вычислите gcd(m/a_i, a_i). Количество, которое вы ищете, является максимальным из этих значений.
Я не доказал, что это всегда так, но в вашем примере это работает:
m=2*4*5*15=600,
max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5
ПРИМЕЧАНИЕ. Это неверно. Если число a_i имеет коэффициент p_j, повторяющийся дважды, и если два других числа также содержат этот коэффициент, p_j, вы получите неверный результат p_j^2 insted из p_j. Например, для набора 3, 5, 15, 25 вместо 5 вы получите 25.
Однако вы все равно можете использовать это, чтобы быстро отфильтровать номера. Например, в приведенном выше случае, как только вы определяете 25, вы можете сначала выполнить исчерпывающий поиск a_3=25 с помощью gcd(a_3, a_i), чтобы найти реальный максимум, 5, а затем отфильтровать gcd(m/a_i, a_i), i!=3, которые меньше или равный 5 (в приведенном выше примере это отфильтровывает все остальные).
Добавлен для уточнения и обоснования:
Чтобы понять, почему это должно сработать, обратите внимание, что gcd(a_i, a_j) делит gcd(m/a_i, a_i) для всех j!=i.
Позвоните gcd(m/a_i, a_i) как g_i и max(gcd(a_i, a_j),j=1..n, j!=i) как r_i. То, что я говорю выше, g_i=x_i*r_i, а x_i - целое число. Очевидно, что r_i <= g_i, поэтому в операциях n gcd мы получаем верхнюю оценку для r_i для всех i.
Вышеуказанное утверждение не очень очевидно. Давайте рассмотрим его немного глубже, чтобы понять, почему это так: gcd a_i и a_j является произведением всех простых факторов, которые появляются как в a_i, так и a_j (по определению). Теперь умножьте a_j на другое число, b. Gcd a_i и b*a_j либо равно gcd(a_i, a_j), либо кратно ему, потому что b*a_j содержит все простые множители a_j и еще несколько простых факторов, внесенных b, что также могут быть включены в факторизацию a_i. На самом деле, gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j), я думаю. Но я не вижу способа использовать это.:)
Во всяком случае, в нашей конструкции m/a_i является просто ярлыком для вычисления произведения всех a_j, где j=1..1, j!=i. В результате gcd(m/a_i, a_i) содержит все gcd(a_i, a_j) как фактор. Итак, очевидно, что максимум этих индивидуальных результатов gcd будет делить g_i.
Теперь наибольший интерес для нас представляет наибольший g_i: он либо сам максимум gcd (если x_i равен 1), либо хороший кандидат для того, чтобы быть одним. Для этого мы выполняем другие операции n-1 gcd и вычисляем r_i явно. Затем мы отбрасываем все g_j меньше или равно r_i в качестве кандидатов. Если у нас нет другого кандидата, мы закончили. Если нет, мы берем следующий самый большой g_k и вычисляем r_k. Если r_k <= r_i, мы отбрасываем g_k и повторяем с другим g_k'. Если r_k > r_i, мы отфильтровываем оставшиеся g_j <= r_k и повторяем.
Я думаю, что можно построить набор чисел, который заставит этот алгоритм работать в O (n ^ 2) (если мы не отфильтровываем что-либо), но на случайных наборах чисел, я думаю, что он быстро избавится от большие куски кандидатов.
Вы можете использовать Евклидовой алгоритм для поиска GCD двух чисел.
while (b != 0)
{
int m = a % b;
a = b;
b = m;
}
return a;
Если вы хотите альтернативу очевидному алгоритму, то, предполагая, что ваши номера находятся в ограниченном диапазоне, и у вас много памяти, вы можете побить время O (N ^ 2), N - количество значений:
Это говорит вам о максимальном gcd, но не говорит вам, какая из них создала его. Для ввода вашего примера вычисленный массив выглядит следующим образом:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0 0 0 0 0 1
Я не знаю, действительно ли это на самом деле быстрее для входных данных, которые вы должны обрабатывать. Применяемые постоянные факторы большие: привязка к вашим значениям и время для факторизации значения внутри этой границы.
Вам не нужно разлагать каждое значение - вы могли бы использовать memoisation и/или pregenerated список простых чисел. Это дает мне представление о том, что если вы мнимая факторизацию, вам не нужен массив:
Добавление/поиск в наборе может быть O (log N), хотя это зависит от того, какую структуру данных вы используете. Каждое значение имеет коэффициенты O (f (k)), где k - максимальное значение, и я не могу вспомнить, что функция f...
Причина, по которой вы закончили со значением, как только вы встретите его в наборе, состоит в том, что вы нашли число, которое является общим фактором из двух входных значений. Если вы продолжите факторизацию, вы найдете меньше таких чисел, которые не интересны.
Я не совсем уверен, что лучший способ повторить для более крупных факторов. Я думаю, что на практике вам, возможно, придется балансировать: вы не хотите делать их вполне в порядке убывания, потому что неудобно создавать упорядоченные факторы, но вы также не хотите, чтобы на самом деле находили все факторы.
Даже в областях O (N ^ 2) вы можете превзойти использование евклидова алгоритма:
Полностью факторизуйте каждое число, сохраняя его как последовательность показателей простых чисел (так, например, 2 является {1}, 4 является {2}, 5 является {0, 0, 1}, 15 является {0, 1, 1}). Затем вы можете вычислить gcd (a, b), взяв минимальное значение для каждого индекса и умножив его обратно. Не знаю, будет ли это быстрее, чем Евклид в среднем, но может быть. Очевидно, что он использует больше памяти.
Оптимизация, о которой я могу думать,
1) начните с двух самых больших чисел, так как они, вероятно, будут иметь большинство простых факторов и, вероятно, будут иметь наиболее общие первичные коэффициенты (и, следовательно, самый высокий GCD).
2) При вычислении GCD других пар вы можете остановить цикл евклидова алгоритма, если вы окажетесь ниже вашего текущего максимального GCD.
Сверху моей головы я не могу думать о том, как вы можете выработать самый большой GCD пары, не пытаясь разобрать каждую пару отдельно (и немного оптимизировать, как указано выше).
Отказ от ответственности: я никогда раньше не рассматривал эту проблему, и выше не было моей головы. Могут быть лучшие способы, и я могу ошибаться. Я рад обсудить свои мысли более подробно, если кто-то захочет.:)
В этой проблеме вообще нет решения O(n log n). На самом деле наихудший случай - это O(n^2) в количестве элементов в списке. Рассмотрим следующий набор чисел:
2^20 3^13 5^9 7^2*11^4 7^4*11^3
Только GCD последних двух больше 1, но единственный способ узнать, что смотреть на GCD - попробовать каждую пару и заметить, что одна из них больше 1.
Таким образом, вы застряли в скучном наборе "попробуйте каждую пару", возможно, с помощью нескольких умных оптимизаций, чтобы избежать ненужной работы, когда вы уже нашли большой GCD (при этом убедитесь, t пропустите что-нибудь).
С некоторыми ограничениями, например, числа в массиве находятся в заданном диапазоне, скажем, 1-1e7, это возможно в O (NlogN)/O (MAX * logMAX), где MAX - максимально возможное значение в A.
Вдохновленный из ситового алгоритма и наткнулся на него в Hackerrank Challenge - там это делается для двух массивов. Проверьте их редакцию.
Предыдущий ответ: Still O (N ^ 2) - сортировать массив; должен устранить некоторые из ненужных сравнений;
max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
if a[ii] <= max_gcd
break
for jj = ii - 1 : -1 :0 do
if a[jj] <= max_gcd
break
current_gcd = GCD(a[ii], a[jj])
if current_gcd > max_gcd:
max_gcd = current_gcd
Это должно сэкономить ненужные вычисления.
псевдокод
function getGcdMax(array[])
arrayUB=upperbound(array)
if (arrayUB<1)
error
pointerA=0
pointerB=1
gcdMax=0
do
gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
pointerB++
if (pointerB>arrayUB)
pointerA++
pointerB=pointerA+1
until (pointerB>arrayUB)
return gcdMax