Задача
Совершенным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является совершенным числом.
Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.
Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.
Найдите сумму всех положительных чисел, которые не могут быть записаны как сумма двух избыточных чисел.
Решение
Сначала написал функцию определения избыточного числа. Тут опять эти чёртовы делители, как же они надоели :) Всё как всегда, но попутно считаем их сумму.
Затем заранее посчитал все избыточные числа до лимита 28123 и сложил в массив buf.
Всего избыточных чисел получилось без малого 7000, но заранее этого я не знал, поэтому выделил память под массив по максимуму –
int* buf = malloc(LIMIT * sizeof(int));
В своё оправдание хочу сказать, что если вы будете писать это на каком-нибудь Питоне, памяти выделится в разы больше, просто вы об этом знать не будете :) Ну и вообще, эта задача масштабироваться не будет, так как выше лимита уже ничего не требуется.
Далее написал функцию, которая проверяет попарно суммы избыточных чисел из массива:
Несмотря на то, что есть ранний выход по превышению суммы, это всё равно O(N²).
Далее заранее считаю сумму для заведомо подходящих чисел 1..23 (что никакой погоды не делает) и от 25 и до лимита перебираю все числа, проверяя их на совпадение с условием и суммируя.
... и сумма считается правильно, но ОЧЕНЬ долго, порядка 30 секунд. Я ожидал, что будет медленно, но не настолько.
Оптимизация
В качестве эксперимента попробовал перебирать суммы не по порядку, а бинарным поиском. Хотя время выполнения сократилось в разы, всё равно была заметная задержка, поэтому я не стал добивать этот вариант.
Далее я поступил немного нечестно. У меня всё время получался неправильный ответ, и я решил поискать в интернете не решение, а просто правильный ответ, чтобы понять, насколько сильно я промахиваюсь. Но увидев ответ, я краем глаза зацепил и само оптимизированное решение. Не полностью, а только маленький намёк. Но этого намёка оказалось достаточно, чтобы догадаться.
Итак, есть сумма всех чисел от 1 до 28123. Это считается легко. Из этой суммы надо вычесть всё, что не подходит, а именно все суммы пар избыточных чисел, которые не больше лимита.
Например, избыточные числа это 12, 18, 20, 24, 30, 36, 40, 42 и т.д.
Из общей суммы вычитаем: 12+12, 12+18, 12+20, 12+24..., 18+18, 18+20, 18+24, ... 40+42.
Проблема здесь только в том, что разные пары могут давать одну и ту же сумму. Например, 12 + 24 = 36 и 18 + 18 = 36. Но вычесть её нужно только один раз. Поэтому здесь потребуется, как в некоторых прошлых задачах, кеш уже использованных чисел. По нему проверяется, было число уже вычтено или нет.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: