Greatest Common Divisor

Q: Какова временная сложность алгоритма Евклида?

Он выполняется за O(log(min(a, b))) шагов, поскольку каждые два шага как минимум вдвое уменьшают большее число. Худший случай — пара последовательных чисел Фибоначчи. Для чисел до 10^9 это не более 43 шагов, а алгоритм использует O(1) дополнительной памяти.

Q: Почему gcd(a, b) равно gcd(b, a % b)?

Запишите a = q × b + r , где r = a % b . Число, делящее a и b , делит a - q × b , то есть r . Число, делящее b и r , делит q × b + r , то есть a . У обеих пар одинаковые общие делители, поэтому у них одинаковый наибольший общий делитель.

НовичокМатематика и моделирование

+10

Даны два положительных целых числа a и b. Верните их наибольший общий делитель: наибольшее целое число, на которое оба числа делятся без остатка.

Например, числа, на которые делятся и 8, и 12, — это 1, 2 и 4, поэтому ответ — 4.

Функция

gcd(a: integer, b: integer) → integer

ainteger: первое положительное целое число
binteger: второе положительное целое число
Возвращаетinteger: наибольшее целое число, на которое делятся и a, и b

Ограничения

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Примеры

Ввод: a = 12b = 18
Вывод: 6
Пояснение: Делители 12 — это 1, 2, 3, 4, 6 и 12; делители 18 — это 1, 2, 3, 6, 9 и 18. Наибольшее число в обоих списках — 6.

Ввод: a = 17b = 5
Вывод: 1
Пояснение: 17 и 5 — оба простые и разные числа, поэтому единственный общий делитель — 1.

Ввод: a = 42b = 42
Вывод: 42
Пояснение: Число делит само себя, и ничто большее, чем 42, не может делить 42, поэтому наибольший общий делитель 42 и 42 равен 42.

+14 скрытых тестов при отправке

Дополнительный вопрос

Можешь расширить алгоритм Евклида так, чтобы он также возвращал целые числа x и y, для которых выполняется a × x + b × y = gcd(a, b)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Определение предлагает проверять кандидатов по одному, и для небольших чисел это работает. Однако при a и b до 10^9 два больших числа, у которых нет общих делителей, потребуют миллиард попыток. Наблюдение Евклида, что gcd(a, b) равно gcd(b, a % b), настолько быстро уменьшает числа, что для любой пары чисел до 10^9 потребуется не более 43 шагов.

Обратный отсчёт от меньшего числа

Верно, но не успевает на самых больших тестах

Идея

Общий делитель не может быть больше меньшего из двух чисел, потому что делитель b не больше b. Поэтому начни с кандидата d, равного min(a, b), и уменьшай его на единицу, пока он не будет делить оба числа. Поскольку ты проверяешь кандидатов сверху вниз, первый подходящий и будет наибольшим.

Для 12 и 18 ты проверяешь 12 (оно не делит 18), затем 11, 10, 9, 8 и 7 — они не подходят, и останавливаешься на 6. Цикл всегда завершается, потому что 1 делит любое число.

Затраты определяются количеством кандидатов. Для 999999937 и 999999929, двух простых чисел, ответ равен 1, а цикл выполняется почти 10^9 раз. Для самых больших тестов это слишком медленно.

Алгоритм

Установи d равным меньшему из a и b.
Пока a % d или b % d не равно 0, вычитай 1 из d.
Верни d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

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

Идея

Запишите a = q × b + r, где r = a % b. Любое число, которое делит и a, и b, также делит r = a - q × b. Любое число, которое делит и b, и r, также делит a = q × b + r. Поэтому пары (a, b) и (b, r) имеют в точности одни и те же общие делители, а значит, и наибольший общий делитель.

Замените (a, b) на (b, a % b) и повторяйте, пока b не станет равным 0. Любое число делит 0, поэтому gcd(a, 0) = a, и ответом будет a. Для чисел 12 и 18: (12, 18) превращается в (18, 12), затем в (12, 6), затем в (6, 0), и ответ — 6. На первом шаге числа меняются местами автоматически, если a меньше, поэтому сортировать их не нужно.

За каждые два шага большее число как минимум уменьшается вдвое, поэтому цикл выполняется O(log(min(a, b))) раз. Самый медленный случай — это соседние числа Фибоначчи, например 701408733 и 433494437, и даже для них требуется всего 42 шага.

Алгоритм

Пока b не равно 0, вычисляй r = a % b.
Присвой a = b и b = r.
Когда b достигнет 0, верни a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Ловушки и крайние случаи

Алгоритм короткий, поэтому ошибки связаны с обновлением значений и условием остановки.

Неправильный порядок обновления. a = b, а затем b = a % b вычисляет b % b, что всегда равно 0, и возвращает b. Сначала сохраните остаток во временной переменной или присвойте оба значения одновременно.
Возврат b вместо a после завершения цикла. В этот момент b равно 0.
Остановка обратного отсчёта на 2 или начало с max(a, b). В первом случае пропускаются взаимно простые пары, например 17 и 5; во втором тратится время на кандидаты, которые не могут делить меньшее число.
Использование повторного вычитания вместо остатка. Тогда для gcd(10^9, 1) потребуется миллиард вычитаний; оператор % выполняет их все за один шаг.

Частые вопросы4

Какова временная сложность алгоритма Евклида?

Он выполняется за O(log(min(a, b))) шагов, поскольку каждые два шага как минимум вдвое уменьшают большее число. Худший случай — пара последовательных чисел Фибоначчи. Для чисел до 10^9 это не более 43 шагов, а алгоритм использует O(1) дополнительной памяти.

Почему gcd(a, b) равно gcd(b, a % b)?

Запишите a = q × b + r, где r = a % b. Число, делящее a и b, делит a - q × b, то есть r. Число, делящее b и r, делит q × b + r, то есть a. У обеих пар одинаковые общие делители, поэтому у них одинаковый наибольший общий делитель.

В чём разница между НОД и НОК?

Наибольший общий делитель — это наибольшее число, на которое делятся оба входных значения; наименьшее общее кратное — это наименьшее число, на которое делятся оба входных значения. Они связаны формулой gcd(a, b) × lcm(a, b) = a × b, поэтому, найдя НОД, можно вычислить НОК по формуле a / gcd(a, b) × b.

Каков НОД двух взаимно простых чисел?

Два числа взаимно просты, если их наибольший общий делитель равен 1, то есть у них нет общих простых множителей. Любые два различных простых числа взаимно просты, как и любые два последовательных целых числа, например 8 и 9.

Python

def gcd(a, b):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

a = 12
b = 18

Ожидается