d1zz7
@d1zz7

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

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


Не могу понять одно, что такое максимальная сумма делителей?)
  • Вопрос задан
  • 113 просмотров
Решения вопроса 2
GavriKos
@GavriKos
Делитель числа А - число Б, при делении на которое числа А получается целое число. И у А может быть много делителей.

У числа 8 делители - 1, 2, 4, 8. Их сумма - 15
У числа 9 делители - 1, 3, 9. Их сумма - 13.
У числа 8 сумма делителей больше
Ответ написан
wataru
@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) - тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы