Ловля пауков

Автор задачи и разработчик: Егор Юлин

Поймем, что означает условие про возможность распределить корм поровну вне зависимости от количества пауков. Если для любого $$$t$$$ от $$$1$$$ до $$$k$$$ есть возможность распределить $$$m - 1$$$ порций корма на $$$t$$$ пауков поровну, то $$$m - 1$$$ делится на $$$t$$$ для любого $$$t$$$ от $$$1$$$ до $$$k$$$.

Следовательно, если мы выбрали какое-то количество корма $$$m$$$, то для каждого $$$t$$$ от$$$1$$$ до $$$k$$$ для выбранного $$$m$$$, $$$m - 1$$$ должно делится на $$$t$$$ (так как один корм мы отдали на анализ, а оставшееся количество должны поровну распределить между пауками). И теперь наша задача сводится к поиску такого $$$m$$$, что

  1. $$$m \leqslant n$$$;
  2. $$$m - 1$$$ делится на все числа от $$$1$$$ до $$$k$$$.

Давайте вместо этого искать подходящий $$$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$$$, при которой это происходит):

  1. $$$k \geqslant 43$$$, а тогда $$$\mathtt{lcm}(1, 2, \ldots, k) > 10^{18}$$$, и единственное подходящее нам $$$m'$$$ — это $$$0$$$, так как $$$m' \leqslant n - 1 < 10^{18}$$$;
  2. $$$k < 43$$$, тогда можно «по-честному» с помощью последовательного применения алгоритма Евклида вычислить интересующий нас $$$\mathtt{lcm}(1, 2, \ldots, k)$$$ и взять максимальное число, не превосходящее $$$n - 1$$$, которое на него делится — это будет $$$$$$m' = (n - 1) - ((n - 1) \bmod \mathtt{lcm}(1, 2, \ldots, k)) \text{.}$$$$$$

Таким образом, решение работает в общем случае за $$$\mathcal{O}(k \log k)$$$.