Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Квадраты

НОД и алгоритм Евклида

Квадраты

Ограничения: время – 1s/Java 2s, память – 8MiB

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, 1 ≤ A, B ≤ 231 − 1). Мальчик Сеня очень любит резать прямоугольники с особым цинизмом, и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты. Сколько же он нарежет квадратов?
Ввод
Числа A и B.
Вывод
Количество получившихся квадратов.

Пример ввода

1 2

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

2
Источник: Турнир "Экспонента-2006"