e-olymp 2612. Разрезание на квадраты

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

Входные данные

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

Выходные данные

Требуется вывести количество квадратов.

Тесты

Входные данные Выходные данные
12 4 3
15 3 5
20 20 1
8 12 3

Код программы

 

Решение задачи

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

  • Высота равна ширине
  • Высота больше ширины
  • Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

  • Задача на сайте e-olymp
  • Код решения в Ideone