Codeforces Round 296 (Div. 2) |
---|
Закончено |
Как-то раз, сидя на не самом интересном уроке по математике, Вася собирал оригами из прямоугольного листа бумаги a мм × b мм (a > b). Как правило, первым шагом при сборке оригами является получение квадратной заготовки из прямоугольного листа бумаги путём сгибания вдоль биссектрисы прямого угла и отрезания лишней части.
Собрав бумажный кораблик из квадратной заготовки, Вася обратил внимание на оставшуюся полоску бумаги (a - b) мм × b мм. Ему пришла в голову мысль использовать аналогичным образом эту полоску для создания оригами, а затем оставшуюся (если такая образуется) и так далее. В тот момент, когда в качестве остатка у него окажется квадратный фрагмент бумаги, он соберёт из него последний кораблик и остановится.
Можете ли вы определить, сколько всего корабликов соберёт Вася за урок?
В первой строке входных данных записаны два целых числа a, b (1 ≤ b < a ≤ 1012) — размеры исходного листа бумаги.
Выведите единственное целое число — количество корабликов, которые соберёт Вася.
2 1
2
10 7
6
1000000000000 1
1000000000000
Иллюстрации к первому и второму тесту из условия.
Название |
---|