Число называется избыточным, если сумма его собственных делителей (всех делителей, кроме самого числа) больше него самого. Наименьшее избыточное число - 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
Примеры
Ввод:
limit = 23
Ожидаемый вывод:
expected = 276
Ввод:
long long limit = 23;
Ожидаемый вывод:
long long expected = 276;
Ввод:
long limit = 23;
Ожидаемый вывод:
long expected = 276;
Пояснение
Никакие два избыточных числа не дают в сумме 23 или меньше, поэтому подходят все числа: 1 + 2 + ... + 23 = 276.
Ввод:
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. Следуйте условию и ограничениям выше.