Нетрудно заметить, что если $$$t_{i + 1} - t_i \leq m$$$, то задачи $$$i$$$ и $$$i + 1$$$ будут сданы либо в один день, либо в соседние дни, а для того, чтобы условие не выполнялось, необходимо, чтобы какие-то два соседних момента времени находились в разных не соседних днях (тогда в день между ними не будет сдана ни одна задача). Если же $$$t_{i + 1} - t_i \ge 2m$$$, очевидно, что между этими двумя моментами времени точно есть день, в который мы ничего не сдадим. Остаётся последний случай: $$$m \lt t_{i + 1} - t_i \lt 2m$$$. В этом случае "плохие" дни могут начинаться с момента $$$t_i + 1$$$ до момента $$$t_{i + 1} - m$$$.

Дальше нам каким-то образом нужно найти такой часовой пояс, чтобы никакой день в нём не начинался в "плохой" отрезок часов. Понятно, что для каждого "плохого" отрезка часов, область часовых поясов, которые он портит, представляет из себя циклически отрезок т.е. 1 или 2 обычных отрезка. Чтобы найти часовой пояс, который не испортится, можно использовать дерево отрезков (неявное или на сжатых координатах) с прибавлением на отрезке.

Асимптотика: $$$O(n \log n)$$$ (если сжать координаты) или $$$O(n \log C)$$$ (если написать неявное ДО).

Код: https://pastebin.com/CSh2xQQr

Построим дерево отрезков с $$$2^{20}$$$ листов. Пусть $$$k_i$$$ — $$$i$$$-й бит очередного параметра запроса.

Покажем, что достаточно легко модифицировать обычный обход дерева отрезков, чтобы он делал то, что нужно в этой задаче. Предположим, что в некоторый момент мы оказались в вершине $$$v$$$, которая отвечает за отрезок $$$[l; r]$$$, и которая лежит в запросе не целиком.

Пусть $$$m$$$ — левый конец правого ребёнка этой вершины, т.е. $$$\frac{l + r + 1}{2}$$$. Если $$$v$$$ находится на высоте $$$h$$$ (листы находятся на высоте $$$0$$$), то все натуральные числа на отрезке левого ребёнка имеют 0 в $$$h - 1$$$ разряде битовой записи, а все натуральные числа на отрезке правого ребёнка имеют 1 в $$$h - 1$$$ разряде битовой записи.

Отсюда следует следующее. Пусть мы сейчас находимся в $$$v$$$ и $$$k_{h - 1}$$$ равен $$$1$$$. В таком случае, левый и правый ребёнок $$$v$$$ "обменяются" отрезками запроса, т.е. если часть запроса в левом ребёнке была равна $$$[l_1; r_1]$$$, а в правом — $$$[l_2, r_2]$$$, то после применения $$$\oplus k$$$ эти части превратятся в $$$[l_1 + (m - l); r_1 + (m - l)]$$$ и $$$[l_2 - (m - l); r_2 - (m - l)]$$$ соответственно.

Кажется, что после такой модификации, запрос к ДО все ещё должен работать за $$$O(n)$$$, но я не до конца умею это пруфать :/

Pro tip: поскольку ввод в этой задаче достаточно большой (больше 7M интов), неплохо бы перестраховаться и заюзать шаблон на быстрый ввод.

Асимптотика: $$$O(qn)$$$.

Код: https://pastebin.com/prQzfApA

Группы 1-2: делаем все запросы втупую, после каждого запроса считаем ответ, используя ДП на DAG-е.

Группа 7: Нетрудно заметить, что в любой момент времени все рёбра будут образовывать множество отрезков из сонаправленных рёбер. Отрезок из $$$n$$$ рёбер вносит в ответ вклад $$$F(n) = \frac{n(n + 1)(n + 2)}{6}$$$. Нетрудно доказать, что все запросы удаляют сколько-то отрезков и образуют $$$O(1)$$$ новых, т.е. все отрезки можно поддерживать в сете интервалов.

Асимптотика: $$$O((n + q) \log n)$$$.

Код: https://pastebin.com/1BmTfAPC

Пусть $$$l(x)$$$ — наименьшая позиция в порядке сдачи задач, на которой может стоять задача сложности $$$x$$$; $$$r(x)$$$ — наибольшая позиция. Нетрудно доказать, что в таком случае, задача сложности $$$x$$$ может находиться на любой позиции $$$l(x) \leq p \leq r(x)$$$.

Наименьшую позицию можно получить, если в каждый день, когда задача сложности $$$x$$$ ещё не разблокирована, мы будем решать не больше одной задачи (ноль, если все доступные задачи уже решены). Аналогично, наибольшую позицию можно получить, если каждый день, когда сложность $$$x$$$ недоступна, решать не более одной задачи, затем решать оставшиеся задачи сложности $$$\gt x$$$ по одной, а затем в один день решить все доступные в этот день задачи, решив задачу сложности $$$x$$$ последней.

Всё вышеописанное нетрудно посчитать за $$$O(n)$$$ (например, используя метод двух указателей) или за $$$O(n \log n)$$$ (например, используя мапы).

Асимптотика: $$$O(n)$$$ или $$$O(n \log n)$$$.

Код: https://pastebin.com/SLdejsjB

Самая первая идея, которая приходит в голову — поскольку различных цветов не так уж и много, можно сделать перебор/отжиг/ещё что-то смешное. Давайте остановимся на переборе. Но чтобы делать его быстро, нужно заметить несколько интересных утверждений.

Утверждение 1: если рёбер какого-то цвета достаточно много (например, $$$\gt 21$$$), то можно не перебирать рёбра этого цвета, т.к. если найдётся разноцветный лес с рёбрами всех остальных цветов, то количество рёбер, которые теоретически могут "испортить" лес при добавлении, будет $$$\leq \frac{8 \cdot 7}{2} - 7 = 21$$$ (например, если уже имеющиеся рёбра составляют бамбук длины 7).

Утверждение 2: теперь посмотрим на структуру перебора. Заметим, что есть сделать рекурсивный перебор всех возможных вариантов, а не просто выбор $$$k$$$ наборов рёбер, то можно отсечь какие-то плохие варианты. Также утверждается, что перебор цветов в порядке неуменьшения количества рёбер с таким цветов будет работать достаточно хорошо.

Утверждение (скорее совет) 3: в этой задаче не нужны сложные структуры или рандом. СНМ за квадрат работает достаточно быстро на таких мелких размерах графов (а ещё его очень удобно откатывать).

Следуя вышеописанным советам, для каждого запроса можно достаточно быстро находить нужное множество рёбер (если оно вообще существует).

Асимптотика: я не знаю, как это оценивать.

Код: https://pastebin.com/DGR0etsZ

Будем называть плохими те вершины, для которых на текущий момент уже известно о $$$\gt 1$$$ исходящих рёбер. Нетрудно заметить, что среди любых 4 вершин есть хотя бы одна плохая (т.к. исходящих рёбер $$$6$$$, а вершин $$$4$$$; по принципу Дирихле будет плохая вершина).

Сначала будем спрашивать рёбра между двумя вершинами, которые не являются плохими. Нетрудно заметить, что к тому моменту, когда не останется неиспользованных рёбер между двумя неплохими вершинами, количество неплохих вершин будет $$$\leq 3$$$ и мы потратим не более $$$2n - 3$$$ запросов. Про оставшиеся вершины мы будем узнавать "втупую", то есть перебирать все рёбра между ней и другими вершинами.

Несложно понять, что такое решение работает за $$$5n$$$ запросов в худшем случае, но каким-то образом оно работает за $$$4n$$$ в группах с неадаптивным интерактором.

Асимптотика: $$$O(n^2)$$$, т.к. нужно поддерживать информацию о всех рёбрах, про которые ещё можно спросить на первом этапе решения.

Код: https://pastebin.com/sf39FG7i

Для начала заметим, что ответ можно забинарить (очевидно, что если $$$k$$$ циклов хватит, то и за $$$k + 1$$$ цикл можно сделать). Но как же именно проверять, подходит ли конкретное количество циклов?

Пусть хотим проверить, хватит ли $$$m$$$ циклов. Тогда применим к каждому блоку $$$m$$$ охлаждений на $$$B$$$ градусов. Далее, если $$$A \lt B$$$, проверим, сколько раз можно прибавить к какому-то элементу $$$B - A$$$, чтобы все элементы остались $$$\lt 0$$$. Если это число $$$\le m$$$, то $$$m$$$ циклов не хватит. Если же $$$A \ge B$$$, из каждого элемента будем вычитать $$$A - B$$$, пока тот $$$\ge 0$$$. Если необходимое количество операций $$$\leq m$$$, нам хватит $$$m$$$ циклов, чтобы выполнить условие.

Асимптотика: $$$O(n \log C)$$$.

Код: https://pastebin.com/Nz9uFNJz

Пронумеруем вершины в порядке сортировки по полярному углу. Очевидно, что первым ходом одна вершина удалится и останется $$$n - 1$$$ сторона исходного многоугольника. Что может происходить дальше:

• выбираем какой-то отрезок из подряд идущих сторон исходного многоугольника и удаляем одну из его крайних сторон

• выбираем какой-то отрезок из $$$\gt 1$$$ подряд идущих сторон исходного многоугольника и удаляем две стороны с какого-то из его концов

• выбираем какой-то отрезок из $$$\gt 3$$$ подряд идущих сторон исходного многоугольника и удаляем две стороны из его середины, получая два новых отрезка с суммарной длиной $$$l - 2$$$

После каждого момента множество сторон исходного многоугольника составляет несколько отрезков подряд идущих сторон. Если рассматривать каждый такой отрезок как игру, получаем сумму игр. Чтобы посчитать результат исходной игры, применим теорию Гранди. Так как всего различных игр $$$n$$$, и из каждой не более $$$n$$$ переходов в суммы игр, всё это можно предподсчитать за $$$O(n^2)$$$.

Далее, нам нужно что-то делать с особыми точками. Понятно, что нас не интересуют те секторы, в которых нет особых точек, поэтому будем считать, что в начальном состоянии удалены все такие рёбра $$$AB$$$, что внутри треугольника $$$ABC$$$ не лежит ни одной исходной точки.

Понятно, что при добавлении/удалении особой точки удаляется/добавляется не более одной стороны исходного треугольника -> множество игр в начальной конфигурации можно поддерживать какой-нибудь структурой данных, например сетом интервалов.

Pro tip: поскольку ввод в этой задаче достаточно большой (больше 2M интов), неплохо бы перестраховаться и заюзать шаблон на быстрый ввод.

Асимптотика: $$$O(n^2 + q \log n)$$$.

Код: https://pastebin.com/gXXMFanX

Разделим решение на две части.

Часть 1 (группы 1-2): Пусть $$$dp_{0, v, i}$$$ — максимальная стоимость, которую можно получить, взяв $$$i$$$ рёбер в поддереве вершины $$$v$$$, при этом не взяв никакую пару рёбер с центром в $$$v$$$; $$$dp_{1, v, i}$$$ — аналогичная дпшка, но известно, что какая-то пара рёбер имеет $$$v$$$ в качестве центра. Случай, когда мы используем в паре ребро из $$$v$$$ в его предка (которое не входит в поддерево) нужно учитывать только для таких $$$dp_{1, v, i}$$$, что $$$i \mod 2 = 1$$$.

Достаточно очевидно, как пересчитывать эту динамику за $$$O(sub_v \cdot sub_u)$$$ для вершины $$$v$$$ и его ребёнка $$$u$$$, где $$$sub_i$$$ — размер поддерева вершины $$$i$$$. На самом деле, этого будет достаточно, потому что сумма всех таких слагаемых будет равна $$$O(n^2)$$$.

Часть 2 (группы 4-5): Пусть $$$dp_{l, m}$$$ и $$$dp_{m, r}$$$ хранят все самые выгодные стоимости взятия $$$k$$$ рёбер на полуинтервале вершин $$$[l; r)$$$. Тогда во-первых, $$$dp_{a, b}$$$ "вогнутое" для любых $$$a < b$$$ (массив "вогнут", если $$$a_i - a_{i + 1}$$$ возрастает с увеличением $$$i$$$), т.е. к нему можно применить $$$(max, +)$$$-свёртку за $$$O(n)$$$; во-вторых, $$$dp_{l, r}$$$ можно как раз пересчитать сверткой за $$$O(n)$$$ -> $$$dp_{0, n}$$$ можно посчитать за $$$O(n \log n)$$$, используя технику разделяй-и-властвуй.

Делать $$$(max, +)$$$ свёртку для "вогнутых" массивов можно вот так.

Код: https://pastebin.com/wJAjrsPm

Заметим тот факт, что для любого $$$1 < i \le n$$$ будет выполняться $$$max(p_{0:i}) \ge i$$$. Назовём хорошей позицией такое $$$i$$$, что $$$max(p_{0:i}) = i$$$.

Понятно, что если закончить очередной подотрезок не на хорошей позиции, то само число $$$i$$$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $$$max(p_{0:i})$$$, противоречие. То есть, концы отрезков могут совпадать только с хорошими позициями -> перестановку можно разбить на $$$k$$$ отрезков с необходимым свойством только тогда, когда количество хороших позиций в этой перестановке $$$\ge k$$$. Построение ответа достаточно тривиально — сделаем концами отрезков $$$k$$$ последних хороших позиций.

Асимптотика: $$$O(n)$$$.

Код: https://pastebin.com/05P67xen

Условие задачи можно переформулировать так — найти количество чисел $$$\le a_i$$$, таких, что сумма двух соседних цифр в их записи не превышает $$$10$$$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.

В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.

Асимптотика: $$$O(log_{10}(a_i))$$$ для одного запроса.

Код: https://pastebin.com/YrtJRZMG

В решениях ниже я буду считать, что $$$n = m$$$, поскольку в максимальных тестах это действительно так.

Разобьём решение на 4 части: для групп 1-2, для группы 3, для группы 4 и для групп 4-5.

Группы 1-2: запустим алгоритм Дейкстры на графе. На каждой итерации переберём ребро, исходящее из вершины, и если у него есть продолжение, то прорелаксируем все рёбра, достижимые из текущего по продолжениям. Иначе, релаксируем только рассмотренное ребро.

Асимптотика: вроде бы $$$O(n^2 log n)$$$, но я не умею строго пруфать это.

Группа 3: то же решение, что и для групп 1-2, но поскольку в этой группе рёбра не имеют продолжений, прийти к этому решению гораздо проще + асимптотика лучше.

Асимптотика: $$$O(m log n)$$$.

Группа 4: в этой группе можно написать 0-1 BFS (поскольку все ребра будут иметь вес либо 0, либо 1) или решение для группы 5.

Асимптотика решения с 0-1 BFS: $$$O(n + m)$$$.

Группа 5: представим, что вместо каждого ребра $$$v$$$ у нас есть $$$max(w) + 1$$$ его копий с весами от $$$0$$$ до $$$max(w)$$$. В таком случае, если приходим в $$$v$$$ из копии ребра $$$u$$$ с весом $$$x$$$, то:

• $$$v$$$ является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$max(0, x — 1)$$$

• $$$v$$$ не является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$w_v$$$

Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $$$v$$$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $$$v$$$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $$$v$$$.

Асимптотика: $$$O(m * max(w) * log(m))$$$.

Код: https://pastebin.com/FXeBHdp1

В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники Segment Tree Beats.

Будем считать, что какая-то позиция обновлена в момент времени $$$x$$$, если после $$$x$$$-ой операции на ней появился снег, до $$$x$$$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $$$INF$$$.

Будем хранить дерево отрезков с тремя параметрами для каждой вершины: min_prev_time, max_prev_time и total_time, где min_prev_time — минимальный момент времени, в который обновили какую-то позицию на отрезке; max_prev_time — аналогично предыдущему, но на максимум; total_time — сумма всех total_time на этом отрезке.

Если операция в момент времени $$$t$$$ имеет тип +, делаем min= $$$t$$$ для всех позиций с $$$l$$$ по $$$r$$$.

Если операция в момент времени $$$t$$$ имеет тип -, делаем total_time += $$$t$$$ — prev_time и prev_time = $$$INF$$$ для всех позиций с $$$l$$$ по $$$r$$$.

Теперь определимся, какие-же tag/break условия нужно взять. Понятно, что делать min= $$$x$$$ на отрезке, на котором максимум меньше $$$x$$$, не имеет смысла, поэтому break-condition для операции +: max_prev_time < $$$x$$$. Аналогично, tag-condition: min_prev_time > $$$x$$$.

Break-condition для операции -: min_prev_time == $$$INF$$$, tag-condition: min_prev_time == max_prev_time.

Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.

Код: https://pastebin.com/wy0REYfb

В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.

Скажем, что число $$$x$$$ является тяжелым, если оно встречается $$$\ge k$$$ раз в массиве. Отсюда понятно, что тяжёлых чисел не больше $$$n / k$$$.

Предподсчитаем ответ для всех различных пар чисел в массиве, в которых есть хотя бы одно тяжелое число. Понятно, что таких пар будет не больше $$$n * (n / k)$$$. Это можно сделать одним проходом по массиву, храня для каждого тяжелого числа количество уже рассмотренных его копий. Асимптотика: $$$O(n * (n / k))$$$.

После предподсчета начнем обрабатывать запросы. Если в текущем запросе нет ни одного тяжелого числа, можно найти ответ методом указателей за $$$O(k)$$$. Иначе, мы уже посчитали ответ в предподсчете.

Таким образом, получаем сложность решения $$$O(n * (n / k) + q * k)$$$. Если предположить, что $$$n = q$$$, то выгоднее всего будет взять $$$k = \sqrt{n}$$$, получим $$$O((n + q) * sqrt(n))$$$.

Код: https://pastebin.com/mtazYBZW

Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.

Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $$$[l; r]$$$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $$$[0; l - 1]$$$ и $$$[0; r]$$$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.

Получаем решение для 5 группы, которое работает за $$$O(n + q)$$$.

В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства!

Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $$$0$$$ до $$$MOD - 1$$$, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.

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

Взломать такой хеш гораздо труднее, чем полиномиальный хеш, поэтому матрицы 2x2 будет достаточно.

Итоговая асимптотика: $$$O(d^3 * n * log(n))$$$, где $$$d$$$ — выбранный размер матрицы для хеширования.

Код: https://pastebin.com/r71qkqzT

Определим ПСП немного иначе: ПСП называется такая строка, что для любого $$$0 \le i < n$$$ на суффиксе $$$[i:n]$$$ находится ровно $$$(n - i) / 2$$$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).

Из этого определения гораздо легче вывести жадное решение задачи.

Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе $$$[0:p + 1]$$$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.

Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $$$O(n log n)$$$.

Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).

Код: https://pastebin.com/fHn6Nt2S

Переформулируем задачу в более формальный вид. Обозначим за $$$f(l, r)$$$ ответ для отрезка $$$[l; r]$$$. В таком случае, если $$$a_l \ne a_r$$$, нетрудно доказать, что $$$f(l, r) = max(f(l + 1, r) + 1, a_r - a_l)$$$ (случай $$$a_l == a_r$$$ тривиален).

Эту же формулу можно представить немного в другом виде. Для каждого $$$p$$$ в массиве $$$nx$$$ будем хранить самую правую позицию массива, число на которой равно $$$a_p$$$. Пусть $$$x = nx_l$$$, $$$s = (a_r - a_l) + (nx_l - l)$$$. Пока $$$a_x \ne a_r$$$, будем "прыгать" через блок равных элементов ($$$x = nx_{x + 1}$$$), изменяя текущий баланс (прибавляя разницу между новым и старым значением, вычитая длину блока). В те моменты, когда баланс будет меньше $$$0$$$, будем вычитать его из $$$s$$$ и делать снова равным $$$0$$$. Доказательство корректности перехода от $$$f(l, r)$$$ к этому алгоритму я оставляю читателю.

Итак, у нас уже есть достаточно быстрый алгоритм, который получает 76 баллов. Чтобы получить полный балл, можно заметить, что можно построить прыжки через прыжки через блоки равных чисел. А именно, из каждого момента, в котором у нас нулевой баланс, мы будем прыгать в ближайший момент с отрицательным балансом, обновляя ответ и снова приходя в момент с нулевым балансом.

Однако и этого мало, потому что у нас может быть очень много таких моментов. Поэтому, на новых прыжках мы построим бинапы на сумму, а чтобы построить их, пройдемся по блокам равных элементов с деревом отрезков.

Получившееся решение работает за $$$O((n + q) log n)$$$.

Код: https://pastebin.com/HTC0WgSf

Пусть pr — массив простых чисел, где $$$pr_0 = 2, pr_1 = 3$$$ etc.

Нам нужно найти $$$f(n, b)$$$, где $$$f(x, y) = x$$$ при $$$x < pr_y$$$. Функцию можно вычислять по следующей формуле: $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b - 1) + ... + f(n / (pr_{b}^k), b - 1)$$$, где $$$k = floor(log_{pr_b}(n))$$$.

Далее можно заметить, что значения $$$f(n, b)$$$ при достаточно маленьких ($$$\le 2000000$$$) $$$n$$$ будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для $$$b \le 8$$$ (или 9) будет не так много различных чисел, которые в разложении содержат множители не больше $$$pr_b$$$ (а именно, порядка пары десятков миллионов), а значит, все эти числа можно также сохранить в отсортированном массиве и при маленьких b вместо запуска функции находить ответ lower_bound-ом к этому массиву).

Совокупность этих идей при аккуратной реализации даёт 82 балла.

Идеи на 100: заметим, что $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b)$$$ (это очевидно вытекает из прошлой формулы), то есть, можно вычислять значения функции не в глубину, а в ширину. Если прикрутить различные оптимизации к стандартному алгоритму BFS, получится решение, которое на максимальном тесте работает около 3.6 секунд, чего достаточно для получения 100 баллов.

Идеями на 100 со мной поделился grishared, за что я ему крайне признателен.

Код: https://pastebin.com/LzZNhtJq