Имеется натуральное число N. Алиса и Маруся по очереди выписывают на доску…

Пусть в разложении ровно различных простых делителей.

Что значит ход. Выписанное число однозначно определяется своим набором простых делителей. Условие взаимной простоты означает, что этот набор не пересекается с простыми, уже «занятыми» ранее выписанными числами. Значит, ход — это выбор любого непустого набора из ещё свободных простых делителей . Показатели степеней ни на что не влияют: подойдёт, например, произведение выбранных простых.

Кроме того, один раз можно выписать число — оно взаимно просто со всеми, но выписать его можно только один раз, так как числа различны.

Сведение к игре Ним. Есть куча из камней, из неё можно взять любое ненулевое число камней (занять любой набор простых). Есть ещё куча из одного камня (число ). Это Ним из двух куч: и .

Кто выигрывает. Проигрывает первый игрок (то есть Алиса) тогда и только тогда, когда XOR размеров куч равен нулю:

Проверка: () — Алиса пишет , и Маруся ходить не может, значит Маруся проигрывает. При () — что бы ни сделала Алиса (написала или степень ), Маруся делает второй ход (пишет степень или ), и Алиса проиграла. При Алиса может выиграть: она сводит позицию к двум одинаковым кучам, например, при берёт один простой, остаются кучи и .

Подсчёт. Нужны вида ():

• простые числа до : ,,,,,,,,,,,,,,,,,,,,, — их ;
• степени двойки: — ;
• степени тройки: — ;
• степень пятёрки: — ;
• степень семёрки: — .

Всего: .