Оптимальный способ уменьшить любое число до 0

Question

Учитывая два числа n и m, разрешена только одна операция, т.е.

Мы можем только вычесть кратное меньшего числа, и оно не может быть равным нулю, то есть, по крайней мере, 1 нужно вычитать за каждый ход.

Как найти оптимальный путь для уменьшения любого из чисел до 0?

Я пытался использовать следующие правила:

• если gcd(m, n) == min(m, n), то 1 ход
• если (n % (m % n) == 0 and n + (m % n) < m), то 2 оборота

if(__gcd(a, b) == min(a, b) || __gcd(a, b) == 1 || (n % (m % n) == 0 && n + (m % n) < m))
   cout << "Win";
else
   cout << "Lose";

Ожидаемый результат показывает, если кто-то начинает с начала, и 2 игрока играют, выигрывает или проигрывает первый игрок, учитывая, что каждый из них играет оптимально

Например, 1022 *

1 1
Win
4 4
Win
4 6
Lose

Answer 1

В соответствии с вашим вопросом, есть только два случая:

1. если начать игру с меньшим числом, он выиграет в 1-м ходу.
2. Если большое число начать игру, то если gcd (м, н) == мин (м, н)
   затем Larger выигрывает в 1-м ходу еще во втором ходу маленький выиграет