5.2. Вычисление НОК и НОД

Наибольший общий делитель

Наибольший общий делитель двух положительных целых чисел и — это самое большое целое число , на которое можно поделить и без остатка. Двадцать три века назад греческий математик Евклид впервые описал, как найти самый большой общий делитель.Однако нам до сих пор неизвестно имя математика, разработавшего этот алгоритм за век до Евклида. Спустя много веков алгоритм Евклида ещё раз обнаружили индийские и китайские астрономы. Теперь эффективный алгоритм, вычисляющий наибольший общий делитель, — важный ингредиент для современных криптографических алгоритмов.

Ваша задача — использовать алгоритм Евклида для вычисления .

• Формат ввода: Целые числа и (разделённые пробелом).
• Формат вывода: .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
18 35	1

Пример 2

Ввод	Вывод
28851538 1183019	17657

— Числа 18 и 35 не обладают общими нетривиальными делителями.
— , .

Примитивный алгоритм для вычисления наибольшего общего делителя

Простой, но ужасно медленный способ вычислить наибольший общий делитель:

GCD(a, b):
    for d от min(a,b) вниз до 1:
        if a % d == 0 and b % d ==0: // d делит a и d делит b
            return d

💡 Остановитесь и подумайте:
Если вы вычислили , можете ли вы сразу найти ?

Рисунок к задаче даёт нам простую, но чрезвычайно важную подсказку: если и , и можно разделить на , значит и можно разделить на . Оказывается, что верно и обратное.

✒️ Упражнение:
Докажите, что при .

Это наблюдение позволяет нам вычислить наибольший общий делитель,отнимая меньшее число от большего снова и снова.В конце концов одно из чисел дойдет до нуля. В таком случае мы просто возвращаем другое число (если , то ).

GCD(a, b):
    while a > 0 and b > 0:
        if a >= b:
            a = a−b
        else:
            b = b−a
    return max(a,b)

✒️ Упражнение:
Насколько этот алгоритм быстрый?

Этот алгоритм всё ещё слишком медленный. Например, при и он продолжает отнимать от — более миллиона раз (в то время как изначальный алгоритм находит наибольший общий делитель при и моментально), так как ему нужно только пройти через . Но не беспокойтесь. Сейчас мы сделаем наш алгоритм эффективнее.

💡 Остановитесь и подумайте:
Что мы получим в итоге, если мы продолжим отнимать
от ?

Правильно! Мы получим 6 — остаток при делении на 7.

💡 Остановитесь и подумайте:
Если вы вычислили , можете ли вы сразу же найти ? Например, будет . Каково отношение между и ?

Алгоритм Евклида

Сказанное выше приводит нас к алгоритму Евклида.

GCD(a, b):
    while a > 0 and b > 0:
        if a >= b:
            a = a % b
        else:
            b = b % a
    return max(a,b)

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

💡 Остановитесь и подумайте:
Докажите, что при верно . Рассмотрите два случая: и .

Следовательно, после максимум итераций или , или дойдёт до нуля. Так как , .

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

GCD(a, b):
    if a = 0 or b = 0:
        return max(a,b)
    return GCD(b,a mod b)

Наименьшее общее кратное

Наименьшее общее кратное для двух положительных целых чисел и — это самое маленькое целое число , которое можно разделить и на , и на .

Рисунок выше демонстрирует для каждой пары чисел , и , а также наименьшее общее кратное для всех трёх. Рисунок ниже показывает наибольший общий делитель для этих же чисел.

💡 Остановитесь и подумайте:
Какова связь между и ?

• Формат ввода: Целые числа и (разделённые пробелом).
• Формат вывода:
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
6 8	24

Пример 2

Ввод	Вывод
761457 614573	467970912861

— Среди всех положительных целых чисел, которые можно разделить и на 6, и на 8 (например, 48, 480 и 24), 24 — наименьшее число.
— Совет: для деления целых чисел в Python3 используйте // (вместо /)

Решение

Для обоснования соотношения рассмотрим разложение и на простые множители.

Если простое входит в разложение в степени и в разложение — в степени , то делится на , а должно делиться на . Для завершения обоснования формулы стоит использовать соотношение .