Задание 7. Имеется натуральное число N. Алиса и Маруся по очереди выписывают на доску различные натуральные числа по следующему правилу: каждое выписанное число должно быть делителем N и при этом быть взаимно просто со всеми числами, уже выписанными на доску. Алиса ходит первой. Проигрывает тот, кто не может сделать ход. Сколько существует натуральных чисел N, не больших 100, таких, что Маруся имеет возможность выиграть независимо от действий Алисы?

Пусть в разложении N на простые множители содержится k различных простых чисел. Каждый выписанный делитель, больший 1, использует хотя бы один из этих простых множителей. Два таких делителя могут быть выписаны вместе, только если используют непересекающиеся наборы простых множителей. Число 1 можно выписать один раз: оно взаимно просто с любым делителем.

Если k = 1, кроме 1 и степеней единственного простого числа, любые два делителя, большие 1, имеют общий простой делитель. Поэтому в игре есть ровно два хода: один игрок выписывает 1, другой — делитель, больший 1. Выигрывает второй игрок, то есть Маруся.

Если k ≥ 2, Алиса может начать с числа 1. После этого остаётся игра с k различными простыми множителями, которые можно использовать по одному или объединять в группы. При k ≥ 2 позиция после хода Алисы выигрышна для следующего игрока: Маруся может разбить оставшиеся простые множители на ходы так, чтобы после каждого хода Алисы сохранялась позиция, из которой у Маруси есть ответный ход, а последним ходом воспользовалась Алиса. Следовательно, Маруся не может гарантировать победу при любом первом ходе Алисы.

Значит, подходят ровно числа, являющиеся степенями одного простого числа: N = p^a ≤ 100, где p простое и a ≥ 1.

Подсчитаем их по основанию: для 2 — 6 чисел; для 3 — 4; для 5 и 7 — по 2; для каждого из остальных простых чисел от 11 до 100 — по 1. Простых чисел от 11 до 100 — 21.

Итого: 6 + 4 + 2 + 2 + 21 = 35.

Ответ: 35.