Задача 550
Игра в делители

Два игрока играют в игру. Имеется k кучек камней.В свой ход игрок должен выбрать кучку и заменить ее двумя кучками камней, следуя двум условиям:

  • Обе новые кучки должны содержать количество камней больше единицы и меньше количества камней в исходной кучке.
  • Количество камней в каждой из новых кучек должно быть делителем количества камней в исходной кучке.

Первый игрок, неспособный сделать разрешенный ход, проигрывает.
Пусть f(n,k) будет количеством выигрышных позиций для первого игрока при условии идеальной игры, когда игра начинается с k кучек, где каждая содержит от 2 до n камней (включительно).
f(10,5) = 40085.

Найдите f(107,1012).
В качестве ответа приведите остаток от деления полученного числа на 987654321.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net