Величайший GCD между некоторыми числами

Question

У нас есть неотрицательные числа. Мы хотим найти пару с максимальным gcd. на самом деле этот максимум важнее пары! Например, если у нас есть:

2 4 5 15

НОД (2,4) = 2

НОД (2,5) = 1

НОД (2,15) = 1

НОД (4,5) = 1

НОД (4,15) = 1

НОД (5,15) = 5

Ответ 5. 5. 1017 *

Answer 1

Вы можете использовать евклидов алгоритм для нахождения GCD из двух чисел.

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;

Answer 2

Если вы хотите альтернативу очевидному алгоритму, то, предполагая, что ваши числа находятся в ограниченном диапазоне, и у вас достаточно памяти, вы можете побить время O (N ^ 2), N - это число значений:

• Создайте массив малого целочисленного типа с индексами от 1 до максимального ввода. O (1)
• Для каждого значения увеличивайте счетчик каждого элемента индекса, который является фактором числа (убедитесь, что вы не переносите). O (N).
• Начиная с конца массива, сканируйте обратно, пока не найдете значение> = 2. O (1)

Это говорит вам о максимальном значении 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

Я не знаю, действительно ли это быстрее для входов, которые вы должны обрабатывать. Постоянные факторы велики: предел ваших значений и время для факторизации значения в пределах этой границы.

Вам не нужно анализировать каждое значение - вы можете использовать запоминание и / или предварительно сгенерированный список простых чисел. Это дает мне представление о том, что если вы запоминаете факторизацию, вам не нужен массив:

• Создать пустой набор значений int и наилучшее на данный момент значение 1.
• Для каждого входного целого числа:
  • если оно меньше или равно наилучшему на данный момент, продолжайте.
  • проверить, есть ли оно в наборе. Если так, лучше всего пока что = max (лучше всего пока это значение), продолжайте. Если не:
    • добавить его в набор
    • повторить для всех его факторов (больше, чем на данный момент).

Добавление / поиск в наборе может быть 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), взяв минимальное значение для каждого индекса и умножив их обратно. Не знаю, в среднем ли это быстрее, чем Евклид, но это может быть так. Очевидно, он использует больше памяти.

Answer 3

Оптимизация, о которой я могу подумать:

1) начните с двух самых больших чисел, поскольку они, вероятно, имеют наиболее простые факторы и, следовательно, могут иметь наиболее общие простые факторы (и, следовательно, самый высокий GCD).

2) При расчете GCD для других пар вы можете остановить цикл евклидового алгоритма, если вы опускаетесь ниже своего текущего наибольшего GCD.

Сверху головы, я не могу придумать, как вы можете получить самый лучший GCD пары, не пытаясь отработать каждую пару индивидуально (и немного оптимизировать, как указано выше).

Отказ от ответственности: я никогда раньше не сталкивался с этой проблемой, и вышеупомянутое неуместно. Там могут быть лучшие способы, и я могу ошибаться. Я рад обсудить мои мысли более подробно, если кто-нибудь захочет. :)

Answer 4

При некоторых ограничениях, например, числа в массиве находятся в заданном диапазоне, скажем, 1-1e7, это возможно в O (NlogN) / O (MAX * logMAX), где MAX - максимально возможное значение в A.

Вдохновленный алгоритмом сита, и наткнулся на него в Hackerrank Challenge - там это делается для двух массивов.Проверьте их редакцию.

• найдите min (A) и max (A) - O (N)
  , создайте двоичную маску, чтобы отметить, какие элементы A появляются в заданном диапазоне, для O(1) поиск;O (N), чтобы построить;Память O (MAX_RANGE).
• для каждого числа a в диапазоне (мин. (A), макс. (A)):
  для aa = a;аа <макс (А);aa + = a: <ul>
• если aa в A, увеличить счетчик для aa и сравнить его с текущим max_gcd, если counter> = 2 (т.е. у вас есть два числа, делимые на aa);
• хранить два лучших кандидата для каждого кандидата в GCD.
• также может игнорировать элементы, которые меньше текущего max_gcd;

Предыдущий ответ: 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

Это должно сохранить некоторые ненужные вычисления.

Answer 5

В общем случае 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 (при этом следя за тем, чтобы вы ничего не пропустили).

Answer 6

Существует решение, которое бы приняло 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 вместо p_j.Например, для набора 3, 5, 15, 25 в качестве ответа вы получите 25 вместо 5.

Однако вы все равно можете использовать его для быстрой фильтрации чисел.Например, в приведенном выше случае, когда вы определили 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_i1) или хороший кандидат на то, чтобы стать таковым.Для этого мы делаем еще одну 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) (если мы не сможемотфильтровывать что угодно), но на случайных наборах чисел, я думаю, это быстро избавит от больших кусков кандидатов.

Answer 7

псевдокод

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