Обозначим через 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
Примеры
Ввод:
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]].
Ввод:
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. Следуйте условию и ограничениям выше.