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

Дружественные числа

Найдите все пары дружественных чисел, в которых оба числа не превышают заданной границы.

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

  • Строить таблицу сумм собственных делителей для всех чисел до границы
  • Проверять условие пары в обе стороны
  • Не выводить пару дважды и не включать совершенные числа

Условие

Обозначим через s(n) сумму собственных делителей числа n (всех его делителей, кроме самого n). Два различных числа a и b образуют пару дружественных чисел, если s(a) = b и s(b) = a. Самая маленькая такая пара состоит из 220 и 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 и s(284) = 1 + 2 + 4 + 71 + 142 = 220.

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

Вычислять s(n) для каждого n до limit по отдельности медленно. Лучше подходит решето: для каждого d прибавьте d ко всем числам, кратным d и большим d.

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

limit: наибольшее значение, которое может принимать любое из чисел пары.

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

Верните список пар [a, b], где a < b ≤ limit, отсортированный по возрастанию a. Пара попадает в ответ, только если оба числа не больше limit. Совершенные числа (у которых s(n) = n) пар не образуют. Если пар нет, верните пустой список.

Ограничения

1 ≤ limit ≤ 200 000

Примеры

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

Ожидаемый вывод:
expected = [
    [220, 284],
    [1184, 1210]
]
Ввод:
long long limit = 1500;

Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Ввод:
long limit = 1500;

Ожидаемый вывод:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Пояснение

s(220) = 284 и s(284) = 220, а также s(1184) = 1210 и s(1210) = 1184. Обе пары укладываются в границу 1500: [[220, 284], [1184, 1210]].

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

Ожидаемый вывод:
expected = []
Ввод:
long long limit = 250;

Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {};
Ввод:
long limit = 250;

Ожидаемый вывод:
long[][] expected = new long[][] {};

Пояснение

220 не больше 250, но его пара 284 уже больше, поэтому ни одна пара не подходит: [].

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

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

Подсказка 1

Для каждого d от 1 до limit / 2 прибавьте d к суммам для 2d, 3d, 4d и так далее.

Подсказка 2

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

Подсказка 3

Условие a < b выводит каждую пару один раз и отсекает совершенные числа.

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

время O(limit log limit), доп. память O(limit)

Ссылки

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

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

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

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

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

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