lasyaaa

19.10.2022 07:07

Информатика

Есть ответ 👍

Девочка Маша любит вырезать из бумаги различные фигуры. Особенно ей нравятся квадраты. На столе перед Машей лежит бумажный прямоугольник размером m × n сантиметров. Девочка хочет, чтобы на столе остались одни лишь квадраты. Пока это не так, она берёт со стола прямоугольник и одним прямолинейным разрезом отрезает от него квадрат. После этого квадрат остаётся на столе, а с остатком происходит то же самое: если он не квадратный, от него одним прямолинейным разрезом отрезается квадрат, и так далее. Наконец, после того, как очередное разрезание привело к появлению двух квадратов, они оба кладутся на стол, и разрезания заканчиваются.

Сколько квадратов окажется у Маши на столе, когда она закончит разрезания?

Формат ввода
В единственной строке ввода заданы целые числа m и n — стороны исходного прямоугольника в сантиметрах (1 ≤ m, n ≤ 2 000 000 000).

Формат вывода
Выведите одно число — количество квадратов, которые окажутся на столе после всех разрезаний.