printТеория чисел

printЛоскутное одеяло

Ограничения: время – 400ms/800ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Одна замечательная старушка уже много лет радует своих внуков подарками, сделанными собственными руками – лоскутными одеялами. Она собирает ненужные прямоугольные куски текстиля у всех родственников и знакомых и старается так их использовать, чтобы не было никаких остатков. Она разрезает эти куски на квадраты. При этом старушка постепенно пришла к оригинальной технологии, которая не требует специальных предварительных расчетов: каждый раз она отрезает один как можно больший квадрат.
Для заданных размеров прямоугольного куска ткани, определите, сколько квадратов сможет из них вырезать наша замечательная старушка.
Входные данные
В первой строке два целых числа – размеры прямоугольника: `n` и `m`, (`1\ ≤\ n,\ m\ ≤\ 10^9`).
Выходные данные
В первой строке целое число – количество квадратов.

Пример ввода 1

3 7

Пример вывода 1

5

Пример ввода 2

9999 9999

Пример вывода 2

1
Источник: NEERC, Западно-Сибирский четвертьфинал, 2007
loading