Что есть максимальная сумма делителей?

Question

[d1zz7]

Есть задача:

Дано число n. Найдите число из диапазона от 1 до n с максимальной суммой своих делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите минимальное из них.
Пример: Вход 5 -> выход 4. Вход 12 -> выход 12

Не могу понять одно, что такое максимальная сумма делителей?)

Answer 1

[GavriKos]

Делитель числа А - число Б, при делении на которое числа А получается целое число. И у А может быть много делителей.

У числа 8 делители - 1, 2, 4, 8. Их сумма - 15
У числа 9 делители - 1, 3, 9. Их сумма - 13.
У числа 8 сумма делителей больше

Comments

[d1zz7]

Теперь поняяял, спасибо!)

Answer 2

[Wataru]

Кстати, можно подсчитать эту самую сумму для всех чисел от 1 до n за линейную сложность.

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

Далее, используя эти данные, можно подсчитать сумму всех простых делителей используя формулу S=(p1^(k1+1)-1)/(1-p1)*...*(pm^(km+1)-1)/(1-pm) (тут p1^k1...pm^km - разложение числа на простые множители).

Надо считать эту сумму делителей от меньших чисел к большим (обозначим ее S(n)). Тогда S(n) = S(n/p^k)*(p^k*p-1)/(p-1).

Но это так, для любопытных. Я думаю в вашей задаче достаточно для кадого числа проверять все делители до корня (а оставшиеся делители получаются как n/i, если i - делитель до корня). Надо только аккуратно разобрать случай, когда i = sqrt(n) - тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.

Comments

[Alexandroppolus]

Крутое решение )

Используя эти данные можно для каждого числа найти его минимальный простой делитель в максимальной степени, на которую число делится

прикольно, что для всех чисел, у которых мин. простой делитель равен p, среднее значение его степени меньше чем p/(p-1), так что эту степень можно искать обычным циклом, средняя сложность которого будет O(1), хотя у некоторых - O(ln(n))

[Wataru]

Alexandroppolus, круто, я даже не подумал среднюю сложность считать. Есть более наглядный вариант - можно считать за константу всегда, а не в среднем.
Пусть lp(n) - минимальный простой делитель из решета. f(n) - искомая максимальная степень. Если lp(n)==lp(n/lp(n)), то f(n)=f(n/lp(n))*lp(n). Иначе - f(n)=lp(n).

[Alexandroppolus]

Wataru, да, так проще.

Вот ведь - казалось бы, тупая и унылая задача на "цикл в цикле" внезапно имеет такую интересную начинку..