Codeforces: удаление делителей
Добро пожаловать в 12 часть этой серии, если вы пропустили 11 часть, вот ссылка: Часть 11
Постановка задачи
Алиса и Боб играют в игру.
Они начинаются с положительного целого числа n и поочередно выполняют над ним операции.
Каждый ход игрок может вычесть из n один из его делителей, который не равен 1 или н. Игрок, который не может сделать ход в свой ход, проигрывает. Алиса всегда ходит первой.
Обратите внимание, что они вычитают делитель текущего числа при каждом ходе.
Вас просят выяснить, кто выиграет игру, если оба игрока будут играть оптимально.
Проблемная ссылка
Ввод
Первая строка содержит единственное целое число t (1≤t≤10^4) — количество тестовых случаев. Затем следуют t тестовые примеры.
Каждый набор входных данных содержит единственное целое число n (1≤n≤10^9) — начальное число.
Вывод
Для каждого теста выведите «Алиса», если Алиса выиграет игру, или «Боб», если выиграет Боб, если оба игрока играют оптимально.
Пример
Ввод:
4
1
4
12
69
Вывод:
Боб
Алиса
Алиса
Боб
Пояснение:
В первом наборе входных данных игра заканчивается немедленно, потому что Алиса не может сделать ход, поэтому выигрывает Боб.
Во втором наборе входных данных Алиса может вычесть 2, что дает n=2, тогда Боб не может сделать ход, поэтому Алиса выигрывает.
В третьем наборе входных данных Алиса может вычесть 3, чтобы n=9. Единственный ход Боба — вычесть 3 и сделать n=6. Теперь Алиса может снова вычесть 3, получив n=3. Тогда Боб не может сделать ход, поэтому выигрывает Алиса.
Подсказка:
Подумайте, как игра будет протекать оптимально в следующих различных случаях. Когда n равно,
- Странный
- Даже и не степень двойки
- Даже и сила двойки.
Решение:
Случай 1.Когда n — нечетное число.
Возможны два подслучая.
Подслучай 1: если n — простое число, это проигрышное состояние, поскольку нет возможных ходов.
Подслучай 2: если n нечетное и не простое число, все его делители должны быть нечетными. Таким образом, единственный возможный ход — вычесть нечетный делитель, что даст четное число. Предположим, что делитель нечетности равен d. Поскольку n делится на d, то n — d также делится на d. После хода получится четное число, не являющееся степенью двойки (случай 2).
Случай 2: когда n — четное число, а не степень двойки.
В этом случае n должен иметь хотя бы один делитель нечетности. Оптимальным ходом будет вычитание этого нечетного делителя, в результате чего получится нечетное число. Сделав этот ход, противник всегда получит нечетное число, которое может быть либо простым числом (Противник ПРОИГРЫВАЕТ), либо противник может сделать ход, как описано в Случае 1, и вернуть четное число, которое не является степенью двойки. Процесс продолжается, и у вас никогда не закончатся ходы, потому что всегда будет хотя бы один нечетный делитель, который нужно вычесть из n.
Таким образом, нечетные числа являются проигрышными, а четные числа, не являющиеся степенями двойки, являются выигрышными.
Случай 3:когда n является степенью числа 2.
В этом случае один из возможных ходов - вычесть делитель так, чтобы полученное число было четным, а не степенью двойки, но это будет выигрышная позиция для противника. Следовательно, оптимальный ход состоит в том, чтобы сделать n вдвое, вычитая n/2 так, чтобы оно оставалось степенью двойки. Этот процесс будет продолжаться до тех пор, пока число не станет равным 2.
Итак, если log2(n) четно, то выигрывает игрок 1, иначе выигрывает игрок 2.
Алгоритм:
- Если число n нечетное (проигрывает игрок 1), выигрывает Боб.
- В противном случае, если число n не является степенью двойки (выигрыш для игрока 1), Алиса побеждает.
- В противном случае, если число n является степенью двойки, а log2(n) четно, Алиса выигрывает.
- В противном случае, если число n является степенью двойки, а log2(n) нечетно, выигрывает Боб.
