Question

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает 9.
ПОЖАЛУЙСТА С ОБЪЯСНЕНИЕМ

Answer 1

Ответ:

117

Объяснение:

В цикле описан алгоритм Евклида: пока числа не равны, из большего вычитается меньшее. Известно, что в результате работы алгоритма Евклида получается наибольший общий делитель двух чисел.

Здесь ищется НОД чисел L = x - 18 и M = x + 36, и должно получиться 9. Если x - 18 делится на 9, то и x делится на 9. Наименьшее число, большее 100 и делящееся на 9, - это 108.

Проверяем:

L = 108 - 18 = 90 = 5 * 18

M = 108 + 36 = 144 = 8 * 18

Нехорошо, НОД равен 18, а не 9.

Берём следующее делящееся на 9 число, x = 117:

L = 117 - 18 = 99 = 11 * 9

M = 117 + 36 = 153 = 17 * 9

Подходит, НОД(L, M) = 9