Начало
ЗадачиПодразделы
Другие разделы
| STL |
| Антагонистические игры |
| Геометрия |
| Графы |
| Динамическое программирование |
| Дихотомия |
| Длинная арифметика |
| Комбинаторика |
| Неклассифицированные |
| Основы |
| Перебор |
| Поиск в глубину |
| Поиск в ширину |
| Последовательности |
| Сортировка |
Дата и время
20/12/2024 15:14:22
Теория чисел
And Now, a Remainder from Our Sponsor Prime Gap Дружественные числа Лоскутное одеяло Простые числа Разложение на простые множители
Лоскутное одеяло
Алгоритм ЭвклидаОлимпиадные задачи на русском языке
| 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
