Верните наибольший общий делитель чисел 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. Следуйте условию и ограничениям выше.