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

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

Следовательно, Маруся выигрывает независимо от действий Алисы ровно при чётном числе различных простых делителей N. Для N=1 такого числа делителей нет, поэтому Алиса сразу проигрывает, и Маруся выигрывает также.

Посчитаем числа до 100. С одним простым делителем их 25: это степени простых чисел. С двумя различными простыми делителями — 37. Всего чисел от 1 до 100: 100; чисел с ровно одним простым делителем, включая 1, — 26; с тремя различными простыми делителями — 8 (произведения троек различных простых, минимальное из которых 2·3·5=30). Поэтому с чётным числом различных простых делителей получается 100−26−8=66.

Ответ: 66.

Поделись с друзьями