Все задачи
Сложно Решено: 0 Процент решений: 0%

Числа, не представимые суммой двух избыточных

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

Чему вы научитесь

  • Вычислять суммы делителей для диапазона с помощью решета
  • Отмечать достижимые суммы в булевом массиве
  • Досрочно прерывать двойной цикл, когда суммы превышают предел

Условие

Число называется избыточным, если сумма его собственных делителей (всех делителей, кроме самого числа) больше него самого. Наименьшее избыточное число - 12: 1 + 2 + 3 + 4 + 6 = 16. Одни числа можно представить в виде суммы двух избыточных чисел (одно и то же число можно взять дважды, как в 24 = 12 + 12), а другие нельзя. Сложите все положительные целые числа от 1 до limit, которые так представить нельзя.

Реализуйте non_abundant_sums(limit).

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

Входные данные

limit: наибольшее число, которое нужно проверить.

Выходные данные

Верните сумму всех n, 1 ≤ n ≤ limit, которые не являются суммой двух избыточных чисел.

Ограничения

1 ≤ limit ≤ 10 000

Примеры

Пример 1
Ввод:
limit = 23

Ожидаемый вывод:
expected = 276
Ввод:
long long limit = 23;

Ожидаемый вывод:
long long expected = 276;
Ввод:
long limit = 23;

Ожидаемый вывод:
long expected = 276;

Пояснение

Никакие два избыточных числа не дают в сумме 23 или меньше, поэтому подходят все числа: 1 + 2 + ... + 23 = 276.

Пример 2
Ввод:
limit = 30

Ожидаемый вывод:
expected = 411
Ввод:
long long limit = 30;

Ожидаемый вывод:
long long expected = 411;
Ввод:
long limit = 30;

Ожидаемый вывод:
long expected = 411;

Пояснение

24 = 12 + 12 и 30 = 12 + 18 не подходят, поэтому ответ 465 − 24 − 30 = 411.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Для каждого i прибавьте i к сумме делителей чисел 2i, 3i, 4i, ...

Подсказка 2

Соберите избыточные числа в порядке возрастания.

Подсказка 3

Для каждой пары a ≤ b прерывайте внутренний цикл, как только a + b превысит предел.

Ожидаемая сложность

время O(limit log limit + A²) для A избыточных чисел, доп. память O(limit)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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