Алгоритм Евклида

⚡️ Рассмотрим следующее задание:

Получив на вход число x, алгоритм приведенный ниже печатает число M. Известно, что x > 150. Укажите наименьшее такое (т. е. большее 150) число x, при вводе которого алгоритм печатает 30.

⚡️Что происходит в программе:

Пока L и M не равны, то мы вычитаем из большего значения меньшее

1-ое действие:
2 * x + 30 − (2 * x − 30), => тогда M станет равно 60

2-ое действие:
(т. к. 2 * x − 30 > 60 по условию), то L станет равно 2 * x − 90

Далее выходит 2 * x − 150, 2 * x − 210, 2 * x − 270
В данном случае, возможно, L станет меньше M

Так как M должно быть 30(НОД=30), то значит: 2 * x − 270 = 30, тогда x = 150, что не подходит по условию(х должен быть больше 150)

Значит, 2 * x − 330 = 30, т. е. x = 180

Ответ: 180