Удвоить или вычесть

Сложная

Фишка стоит в точке (1, 1) бесконечной клетчатой плоскости. За один ход из точки (x, y) её можно переставить в одну из точек: - (x, y − x) - (x − y, y) - (2·x, y) - (x, 2·y) Даны числа goal_x и goal_y. Верните True, если за конечное число ходов фишка может оказаться в точке (goal_x, goal_y), и False иначе.

Пример 1

goal_x=8, goal_y=24 → True

(1, 1) → (1, 2) → (1, 4) → (1, 3) → (2, 3) → (4, 3) → (8, 3) → (8, 6) → (8, 12) → (8, 24).

Пример 2

goal_x=10, goal_y=15 → False

Никакая последовательность ходов не приводит в (10, 15).

Пример 3

goal_x=12, goal_y=5 → True

Ограничения

1 ≤ goal_x, goal_y ≤ 10⁹

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Math Number Theory

Вход

goal_x=8, goal_y=24

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 88 тестов на сервере, включая скрытые.