НОД двух чисел

Даны два натуральных числа. Выведите их наибольший общий делитель.

Одна строка: $a$ и $b$ от $1$ до $10^{18}$.

Одно число.

Алгоритм Евклида: пока $b \ne 0$, заменяем пару $(a, b)$ на $(b, a \bmod b)$. Функция gcd пригодится ещё трижды — в НОК, в счёте взаимно простых и в задаче про пары.