Решение задачи 304
Никита ЖуковскийУсловие:
Имеются три автомата. Получив пару чисел (n,m), первый из них преобразует ее в пару (n,m), второй преобразует в пару (m,n−m), третий -- в пару (m,n+m). Можно ли преобразовать пару (19,86) в пару (12,21)?
Решение:
Заметим, что НОД пары чисел не меняется. Действительно, пусть a,b -- натуральные числа и a>b, обозначим через (a,b) их НОД. Тогда (a,b)=(a-b,b)=(a+b,b). Подробнее можно почитать здесь. НОД чисел 19 и 86 равен 1, а НОД чисел 12 и 21 равен 3, следовательно преобразовать пару (19,86) в пару (12,21) нельзя.
Ответ: Нет.