Введение
Даны два неотрицательных целых числа и , мы хотим найти их наибольший общий делитель (НОД), то есть наибольшее положительное целое число, которое делит оба числа.
Например:
Даны два неотрицательных целых числа и , мы хотим найти их наибольший общий делитель (НОД), то есть наибольшее положительное целое число, которое делит оба числа.
Например:
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Формально,
Здесь символ означает делимость. Например, означает, что делит .
Алгоритм Евклида основан на нескольких простых наблюдениях.
Если одно из чисел равно нулю, то НОД — это другое число.
Порядок чисел не имеет значения.
Предположим, что . Тогда:
Действительно, вычитание из не изменяет общие делители.
Если повторить это вычитание много раз, мы в итоге получим остаток от деления на . Поэтому более быстрая версия:
Используя эту идею, получаем основную рекурсивную формулу:
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int gcd(int a, int b) {
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}