Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
675. Лоскутное одеяло
Алгоритм ЭвклидаОлимпиадные задачи на русском языке
| 17/11/2007 | Тренировка (задачи Западно-Сибирского четвертьфинала 2007) (C) |
| 09/09/2014 | Занятие 2 (D) |
| 27/06/2018 | Лето 2018 - 2 (упрощенное) (D) |
| 02/07/2020 | Лето 2020 - 2 (упрощенное) (D) |
Ограничения: время – 400ms/800ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Одна замечательная старушка уже много лет радует своих внуков подарками, сделанными собственными руками – лоскутными одеялами. Она собирает ненужные прямоугольные куски текстиля у всех родственников и знакомых и старается так их использовать, чтобы не было никаких остатков. Она разрезает эти куски на квадраты. При этом старушка постепенно пришла к оригинальной технологии, которая не требует специальных предварительных расчетов: каждый раз она отрезает один как можно больший квадрат.
Для заданных размеров прямоугольного куска ткани, определите, сколько квадратов сможет из них вырезать наша замечательная старушка.
Входные данные
В первой строке два целых числа – размеры прямоугольника: `n` и `m`,
(`1\ ≤\ n,\ m\ ≤\ 10^9`).
Выходные данные
В первой строке целое число – количество квадратов.
Пример ввода 1
3 7
Пример вывода 1
5
Пример ввода 2
9999 9999
Пример вывода 2
1
