Problema
Sea s(n) la suma de los divisores propios de n (sus divisores distintos del propio n). Dos números distintos a y b son números amigos cuando s(a) = b y s(b) = a. La pareja más pequeña es 220 y 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 y s(284) = 1 + 2 + 4 + 71 + 142 = 220.
Implementa amicable_pair(limit).
Calcular s(n) para cada n hasta limit, uno por uno, es lento. Una criba funciona mejor: para cada d, suma d a cada múltiplo de d mayor que d.
Entrada
limit: el valor máximo que puede tener cualquiera de los dos números de una pareja.
Salida
Devuelve una lista de parejas [a, b] con a < b ≤ limit, ordenadas por a de forma ascendente. Una pareja se incluye solo si ambos números son menores o iguales que limit. Los números perfectos (con s(n) = n) no forman pareja. Si no hay ninguna, devuelve una lista vacía.
Restricciones
1 ≤ limit ≤ 200,000
Ejemplos
Entrada:
limit = 1500
Salida esperada:
expected = [
[220, 284],
[1184, 1210]
]
Entrada:
long long limit = 1500;
Salida esperada:
std::vector<std::vector<long long>> expected = {
{220, 284},
{1184, 1210}
};
Entrada:
long limit = 1500;
Salida esperada:
long[][] expected = new long[][] {
new long[] {220, 284},
new long[] {1184, 1210}
};
Explicación
s(220) = 284 y s(284) = 220, y además s(1184) = 1210 y s(1210) = 1184. Las dos parejas caben por debajo de 1500: [[220, 284], [1184, 1210]].
Entrada:
limit = 250
Salida esperada:
expected = []
Entrada:
long long limit = 250;
Salida esperada:
std::vector<std::vector<long long>> expected = {};
Entrada:
long limit = 250;
Salida esperada:
long[][] expected = new long[][] {};
Explicación
220 no pasa de 250, pero su pareja 284 sí, así que ninguna pareja cabe: [].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Para cada d de 1 a limit / 2, suma d a las sumas de 2d, 3d, 4d, etc.
Pista 2
Para cada a, sea b la suma de sus divisores; comprueba que b esté dentro del rango y que la suma de los divisores de b sea a.
Pista 3
Exigir a < b hace que cada pareja aparezca una sola vez y deja fuera los números perfectos.
Complejidad esperada
tiempo O(limit log limit), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.