Наша Таня громко плачет

Если k = 1, то ответ на задачу, очевидно, , в противном случае будем жадно уменьшать количество файлов жадно.

В каждый момент времени мы можем находиться в одной из трёх ситуаций:

  1. Если n < k, то нам ничего не остается, кроме как n - 1 раз уменьшить число за A, мы можем сделать это за формулой.
  2. Если n > k и n не кратно k, то нам ничего не остается, кроме как уменьшить число за A, эту часть тоже можно сделать за формулой.
  3. Если n кратно k, то нам всегда выгодно сделать переход к за . Если  корректность очевидна. Иначе предположим мы не сделали переход к сейчас, а сделали его на отрезке из числа , тогда мы заплатили . Это или , что не выгоднее перехода сразу к и последующему спуску к числу . Данный переход тоже делается за .

Поскольку в каждой ситуации мы можем побывать не более раз асимптотика решения .