Автор задачи и разработчик: Егор Юлин
Поймем, что означает условие про возможность распределить корм поровну вне зависимости от количества пауков. Если для любого $$$t$$$ от $$$1$$$ до $$$k$$$ есть возможность распределить $$$m - 1$$$ порций корма на $$$t$$$ пауков поровну, то $$$m - 1$$$ делится на $$$t$$$ для любого $$$t$$$ от $$$1$$$ до $$$k$$$.
Следовательно, если мы выбрали какое-то количество корма $$$m$$$, то для каждого $$$t$$$ от$$$1$$$ до $$$k$$$ для выбранного $$$m$$$, $$$m - 1$$$ должно делится на $$$t$$$ (так как один корм мы отдали на анализ, а оставшееся количество должны поровну распределить между пауками). И теперь наша задача сводится к поиску такого $$$m$$$, что
Давайте вместо этого искать подходящий $$$m' = m - 1$$$. Поскольку он делится на все числа от $$$1$$$ до $$$k$$$, то он делится и на $$$\mathtt{lcm}(1, 2, \ldots, k)$$$, где $$$\mathtt{lcm}$$$ означает наименьшее общее частное. Известный факт: наименьшее общее частное выражается через наибольший общий делитель, который можно посчитать алгоритмом Евклида, следующим образом: $$$\mathtt{lcm}(a, b) = \frac{a \cdot b}{\mathtt{gcd}(a, b)}$$$. А тогда вычислить $$$\mathtt{lcm}(1, 2, \ldots, k)$$$ можно, например, за время $$$\mathcal{O}(k \log k)$$$, так:
result = 1
for i = 2..k {
result = result * i / gcd(result, i)
}
Теперь имеет смысл расмотреть два случая (на самом деле не обязательно рассматривать эти случаи явно, можно было просто считать lcm, пока оно не превысит $$$n - 1$$$, но мы в явном виде укажем границу на $$$k$$$, при которой это происходит):
Таким образом, решение работает в общем случае за $$$\mathcal{O}(k \log k)$$$.