Problema
Seja s(n) a soma dos divisores próprios de n (os seus divisores, exceto o próprio n). Dois números diferentes a e b formam um par de números amigos quando s(a) = b e s(b) = a. O menor par é 220 e 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 e s(284) = 1 + 2 + 4 + 71 + 142 = 220.
Implemente amicable_pair(limit).
Calcular s(n) para cada n até limit, um de cada vez, é lento. Um crivo funciona melhor: para cada d, some d a cada múltiplo de d maior que d.
Entrada
limit: o maior valor que qualquer um dos números de um par pode ter.
Saída
Retorne uma lista de pares [a, b] com a < b ≤ limit, ordenada por a em ordem crescente. Um par só entra se os dois números forem no máximo limit. Números perfeitos (em que s(n) = n) não formam pares. Se não houver nenhum par, retorne uma lista vazia.
Restrições
1 ≤ limit ≤ 200 000
Exemplos
Entrada:
limit = 1500
Saída esperada:
expected = [
[220, 284],
[1184, 1210]
]
Entrada:
long long limit = 1500;
Saída esperada:
std::vector<std::vector<long long>> expected = {
{220, 284},
{1184, 1210}
};
Entrada:
long limit = 1500;
Saída esperada:
long[][] expected = new long[][] {
new long[] {220, 284},
new long[] {1184, 1210}
};
Explicação
s(220) = 284 e s(284) = 220, e também s(1184) = 1210 e s(1210) = 1184. Os dois pares cabem abaixo de 1500: [[220, 284], [1184, 1210]].
Entrada:
limit = 250
Saída esperada:
expected = []
Entrada:
long long limit = 250;
Saída esperada:
std::vector<std::vector<long long>> expected = {};
Entrada:
long limit = 250;
Saída esperada:
long[][] expected = new long[][] {};
Explicação
220 não passa de 250, mas o seu par 284 passa, então nenhum par cabe: [].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Para cada d de 1 até limit / 2, some d às somas de 2d, 3d, 4d, e assim por diante.
Dica 2
Para cada a, seja b a soma dos seus divisores; verifique se b está no intervalo e se a soma dos divisores de b é a.
Dica 3
Exigir a < b lista cada par uma única vez e deixa de fora os números perfeitos.
Complexidade esperada
tempo O(limit log limit), espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.