Модуль: НОД (Наибольший общий делитель)


Задача

8 /11


Квадраты


Задача

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, \(1 <= A, B <= 2^{31} - 1\)). Мальчик Сеня очень любит резать прямоугольники с особым цинизмом, и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты.
Сколько же он нарежет квадратов?

Входные данные
Числа A и B, задаются в одной строке через пробел.

Выходные данные
Количество получившихся квадратов.
 

Примеры
Входные данные Выходные данные
1 1 2 2

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64413
Free Pascal4
Java3
Python406
Комментарий учителя