Все задачи
Легко Решена: 1 Процент решений: 50.0%

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

Найдите наибольшее число, на которое делятся оба значения.

Чему вы научитесь

  • Применять алгоритм Евклида с остатками
  • Превращать математическое правило в цикл
  • Понять, почему алгоритм работает быстро

Условие

Верните наибольший общий делитель чисел a и b. Алгоритм Евклида многократно заменяет (a, b) на (b, a mod b), пока b не станет равным 0.

Реализуйте функцию gcd(a, b).

Ввод

a: Первое число. b: Второе число.

Вывод

Верните gcd(a, b). Значение gcd(0, 0) считается равным 0.

Ограничения

0 ≤ a, b ≤ 10¹⁸

Примеры

Пример 1
Ввод:
a = 48
b = 18

Ожидаемый вывод:
expected = 6
Ввод:
long long a = 48;
long long b = 18;

Ожидаемый вывод:
long long expected = 6;
Ввод:
long a = 48;
long b = 18;

Ожидаемый вывод:
long expected = 6;

Пояснение

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, поэтому ответ — 6.

Пример 2
Ввод:
a = 17
b = 5

Ожидаемый вывод:
expected = 1
Ввод:
long long a = 17;
long long b = 5;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long a = 17;
long b = 5;

Ожидаемый вывод:
long expected = 1;

Пояснение

17 и 5 не имеют общих делителей, кроме 1.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

НОД не меняется, если заменить пару на шаг с остатком.

Подсказка 2

Меняйте местами роли двух чисел, пока второе не станет нулём.

Подсказка 3

Обязательно обработайте случай, когда оба входа равны нулю.

Ожидаемая сложность

время O(log min(a, b)), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 HJhettory Jurash Python 970 ms - 3/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.