запихну решение в спойлер.

ну я сразу обозначил этот момент в стартовом посте:


никто тогда не возмутился, значит все согласились )

деления, кстати, тут всегда дают целое число, никаких дробных чисел не будет.

mayton,

если ты ещё раз глянешь формулы, то заметишь, что в расчетах никогда не всплывет число, большее искомой максимальной суммы делителей (которая, в свою очередь, менее чем 2N). Итого для N = MAX_INT нужно только 33 бита на число, ну то есть int64 хватит за глаза. Задачка не про длинную арифметику, а про обычную.

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




Рассмотрим заполнение массива lp.
С простым индексом всё очевидно, он заполняется в ифе на соответствующей итерации внешнего цикла, т.е. один раз.
Если же число i составное, то lp[i] заполнится на внешней итерации j, причем такой, что i == j * p, где p - простое.

Докажем от противного, что такое j только одно для каждого составного i, и любое lp[i] заполняется только один раз.

Допустим, это не так.
Тогда для некоторого i заполнение lp[i] делается на внешних итерациях j1 и j2,
таких что i == (j1 * p1) == (j2 * p2), где p1 и p2 - простые
пусть j1 < j2, тогда p1 > p2
но тогда j1 делится на p2, и значит, LP(j1) < p1, и значит, на внешней итерации j1 внутренний цикл не доберется до простого числа p1 (так как перебираются простые не больше LP(j1)), и не будет затронута ячейка lp[i].
Противуречие.

итак, каждое lp[i] заполняется только один раз. Поскольку во внутреннем цикле каждая итерация заполняет ячейку lp, то всего итераций всех внутренних циклов не более чем n.

Что-то перемудрил, можно проще)

Рассмотрим заполнение массива lp.
С простым индексом всё очевидно, он заполняется в ифе на соответствующей итерации внешнего цикла, т.е. один раз.
Если же число i составное, то lp[i] может заполнится только на внешней итерации вида j == i/p, где p - некоторый простой делитель i.
Заметим, что здесь p <= LP(j), так как во внутреннем цикле перебираются только такие p. Получается, p == LP(i), тогда j = i/LP(i), то есть такое j возможно только одно для каждого i.

Итого, каждое lp[i] заполняется только один раз. Поскольку во внутреннем цикле каждая итерация заполняет ячейку lp, то всего итераций всех внутренних циклов не более чем n.

kealon(Ruslan),

Ага, в Википедии не доказано. Но этот алгоритм хотя бы упоминается, в английской версии его вообще нет )

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

на плюсах, к примеру, в std есть дохрена ништяков. Кучи, деревья, списки, и т.д.

в сабжевом паззле, кстати, его тоже не найти. Есть простой код на 10 строк, который только что разобрали по косточкам.

mayton,

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