Дано натуральное N. Выяснить, у какого целого числа из отрезка 1...N будет наибольшая сумма делителей.

время работы O(N), то есть линейное.

Про память не сказано, но чем меньше тем лучше. Насчет размерности чисел не заморачиваемся, полагаем что любое число поместится в некую "числовую переменную", размер и все операции с которой - О(1)

что это??

на всякий: для каждого числа подразумевается сумма всех его делителей. То есть, к примеру, число 12: делители: 2, 3, 4, 6, 12, их сумма равна 27

один раз. Каждый делитель числа X попадает в сумму делителей числа Х по одному разу.
то же, что и с простыми. Добавлять в сумму делителей числа.
можно добавить и эту единицу - на решение это не влияет.

прикольность известного мне прикольного решения в том, что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N, причем на всё про всё нужно O(N) времени. То есть - О(1) на число.

kealon(Ruslan),

это само собой.
дельная мысль.

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

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


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

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

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 решения). Руслан спросил о линейности алгоритма, я расписал почему считаю этот алгоритм линейным. Полный код чуть позже запилю.