Общий размер плитки

Во дворе школы решили выложить прямоугольную площадку плиткой без подрезки. Размер площадки — a × b (в сантиметрах). Плитки хотят взять квадратные, и чем больше сторона квадрата, тем меньше возни.

Найдите максимальную сторону квадратной плитки, которой можно выложить площадку a × b без остатка.

Важно: числа могут быть большими (ориентируйтесь на 64-битные целые, как на олимпиадах), но в Python это не проблема.

Формат ввода

В одной строке записаны два целых числа a и b.

Формат вывода

Выведите одно целое число — максимальную возможную сторону квадратной плитки.

Ограничения

• 1 ≤ a ≤ 10^9
• 1 ≤ b ≤ 10^9

Пример

Ввод:

12 18

Вывод:

6

Квадратная плитка со стороной x укладывается без подрезки тогда и только тогда, когда x делит и a, и b (то есть a % x == 0 и b % x == 0). Значит, нам нужен самый большой общий делитель двух чисел — НОД(a, b).

Почему это работает: если x — общий делитель, то по стороне a поместится ровно a/x плиток, по стороне b — b/x плиток. Самый большой такой x и даёт «самую крупную плитку».

Как быстро найти НОД: используем алгоритм Евклида. Ключевое наблюдение: НОД(a, b) = НОД(b, a % b). Остаток меньше b, поэтому числа быстро уменьшаются.

План решения:

• Считать a и b.
• Пока b не равно 0, делать замену: a, b = b, a % b.
• Когда цикл закончится, в a лежит НОД; вывести a.

Сложность: O(log(min(a, b))) по времени, памяти почти не нужно.

Частая ошибка: пытаться перебирать все делители до min(a, b) — это слишком медленно на больших числах. Ещё одна грабля — забыть, что нужно именно максимальный общий делитель, а не просто какой-то делитель.