Самый большой нечетный делитель Игра, чтобы проверить, какой игрок выиграет
Два игрока играют в игру, начинающуюся с числа n . На каждом ходу игрок может сделать любой из следующих ходов:
- Разделите n на любой из его нечетных делителей больше 1. Делители числа включают само число.
- Вычтите 1 из n, если n> k, где k <n.
Игрок 1 делает основной ход, выведите «да», если игрок 1 выиграет, в противном случае выведите «нет», если оба играют оптимально. Игрок, который не может сделать ход, проигрывает.
Примеры:
Input: n = 12, k = 1
Output: Yes
Explanation:
Player 1 first move = 12 / 3 = 4
Player 2 first move = 4 – 1 = 3
Player 1 second move = 3 / 3 = 1
Player 2 second move can be done and hence he looses.
Input: n = 1, k = 1
Output: No
Explanation:
Player 1 first move is not possible because n = k and hence player 1 looses.
Подход: Идея состоит в том, чтобы проанализировать проблему для следующих 3 случаев:
- Когда целое число n нечетно , игрок 1 может разделить n на себя, поскольку оно нечетное и, следовательно, n / n = 1, а игрок 2 проигрывает. Обратите внимание, что здесь n = 1 является исключением.
- Когда целое число n четно и не имеет нечетных делителей больше 1, тогда n имеет вид 2 x . Игрок 1 обязан вычесть его на 1, что сделает n нечетным. Итак, если x> 1, выигрывает игрок 2. Обратите внимание, что для x = 1 n - 1 равно 1, поэтому игрок 1 выигрывает.
- Когда целое число n четно и имеет нечетные делители , остается задача проверить, делится ли n на 4, тогда игрок 1 может разделить n на свой наибольший нечетный множитель, после чего n принимает форму 2 x, где x> 1, так что снова игрок 1 побеждает.
- В противном случае n должно иметь вид 2 * p , где p нечетное. Если p простое , игрок 1 проигрывает, поскольку он может либо уменьшить n на 1, либо разделить его на p, что для него будет проигрышем. Если p не является простым числом, то p должно иметь вид p1 * p2, где p1 - простое число, а p2 - любое нечетное число> 1, для которого игрок 1 может выиграть, разделив n на p2.
Ниже представлена реализация описанного выше подхода:
Сложность времени: O (sqrt (n))
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.