НОД, НОК и алгоритм Евклида
В этом уроке все входные данные — неотрицательные целые числа.
Наибольший общий делитель (НОД), , — это наибольшее положительное целое число, которое делит и , и , если хотя бы одно из них не равно нулю.
Любое положительное целое число делит ноль. Поэтому при общие делители чисел и — это в точности делители числа , откуда . Также по соглашению полагаем : в этом случае наибольшего положительного общего делителя не существует.
Числа можно уменьшать, не меняя их общих делителей. При разделим на с остатком и запишем , где — частное, а — остаток.
Любое число, которое делит и , и , также делит . И наоборот: любое число, которое делит и , и , делит . Значит, пары и имеют одни и те же общие делители:
Алгоритм Евклида многократно выполняет эту замену. Второй аргумент на каждом шаге уменьшается, поэтому в конце концов становится равным нулю. Тогда первый аргумент и есть ответ.
На схеме показана работа алгоритма для пары . В каждой строке первое число разбивается на несколько частей, равных второму числу, и остаток. Синий остаток становится вторым аргументом в следующей строке.
Второй аргумент не обязательно уменьшается вдвое за один шаг: на схеме он сначала уменьшается с до . Однако за два шага он уменьшается хотя бы вдвое.
Если , первый шаг меняет числа местами. Когда , обозначим :
Таким образом, алгоритм выполняет операций взятия остатка, в том числе в случаях с нулевыми входными данными.
Задание
Для положительных и рассмотрим другой процесс: будем вычитать меньшее число из большего, пока они не станут равными. Сохраняет ли этот процесс НОД? Остаётся ли число итераций логарифмическим? Обоснуйте оба ответа.
НОД сохраняется: при пары и имеют одни и те же общие делители. Другой случай разбирается аналогично. Оба числа остаются положительными, а их сумма уменьшается, поэтому процесс заканчивается, когда числа становятся равными. Их общее значение — исходный НОД.
Однако оценка числа итераций другая. Для пары потребуется вычитаний. Операция взятия остатка в алгоритме Евклида сразу убирает все полные копии меньшего числа, поэтому для такой пары достаточно одного шага.
НОД связан с общими делителями, а наименьшее общее кратное (НОК), , — это наименьшее положительное целое число, которое делится на оба положительных входных числа. Если хотя бы одно из них равно нулю, полагаем НОК равным нулю, в том числе .
Чтобы установить связь между НОД и НОК, рассмотрим разложение на простые множители. Простое число — это целое число не меньше , у которого нет положительных делителей, кроме и самого себя. Каждое положительное целое число единственным образом раскладывается на простые множители; у числа простых множителей нет.
Для простого числа обозначим через и его показатели степени в разложениях и . Если отсутствует в разложении, соответствующий показатель равен нулю. В общем делителе показатель степени не может превышать , а в НОД он равен именно этому значению. В общем кратном показатель должен быть не меньше , и в НОК он равен именно этому значению.
При умножении НОД на НОК эти показатели складываются. Для каждого простого числа их сумма равна , поэтому произведение равно . Следовательно, для положительных :
Сначала выполняйте деление, затем умножение. Произведение может вызвать переполнение, даже если сам НОК помещается в выбранный тип. При этом — целое число, не превышающее .
Но и итоговое произведение может оказаться слишком большим. Пусть — наибольшее значение типа long long, заданное константой LLONG_MAX, а . При умножение на безопасно тогда и только тогда, когда
Проверяйте это неравенство до умножения. Нулевые аргументы нужно обработать заранее, чтобы ни в этой проверке, ни при делении на НОД не возникло деления на ноль.
Обе операции ассоциативны: результат не зависит от расстановки скобок. Число делит все элементы тогда и только тогда, когда оно делит их НОД. Число является общим кратным всех элементов тогда и только тогда, когда оно кратно их НОК. Эти свойства не зависят от группировки элементов. Принятые соглашения для нуля также сохраняют ассоциативность.
Чтобы найти НОД непустого списка , начните с и последовательно обрабатывайте элементы:
Начальный ноль подходит, потому что . Как только , дальнейшие элементы уже не могут изменить результат.
Для НОК сначала проверьте, есть ли в списке ноль. Если есть, ответ равен нулю. Иначе начните с и последовательно находите НОК текущего и очередного элемента, каждый раз проверяя переполнение. Каждый новый НОК — положительное кратное предыдущего. Поэтому, если промежуточный результат превысил допустимый предел, итоговый результат тоже его превысит.
Если вычисление прекращается при первом переполнении, предварительная проверка на ноль необходима: ноль в оставшейся части списка сделал бы итоговый ответ равным нулю.
Подумайте
Пусть — положительные целые числа и . Обязательно ли ? Если нет, приведите контрпример. Найдите точное условие на НОД каждой пары чисел, при котором это равенство выполняется.
Возьмём , и . Их НОД равен , но НОК равен , тогда как . Ни одно простое число не делит все три числа, но каждый простой множитель встречается в двух из них.
Равенство выполняется тогда и только тогда, когда НОД каждой пары равен : такие числа называют попарно взаимно простыми. Если у чисел нет общих простых множителей, наибольший показатель степени каждого простого числа совпадает с его показателем в произведении. Если же простое число делит хотя бы два числа, его показатель в произведении строго больше наибольшего показателя в разложении отдельного числа. Поэтому произведение больше НОК.
Оба аргумента должны быть неотрицательными и помещаться в тип long long. Функция возвращает , если НОК превышает LLONG_MAX.
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
while (b > 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
long long lcm_safe(long long a, long long b) {
if (a == 0 || b == 0) {
return 0;
}
a /= gcd(a, b);
if (a > LLONG_MAX / b) {
return -1;
}
return a * b;
}