Médio 0 resolvidos 0% de aceitação

Números Amigos

Liste todos os pares de números amigos em que os dois números não passam de um limite.

O que você vai aprender

  • Montar uma tabela com a soma dos divisores próprios de cada número até um limite
  • Verificar uma condição de par nos dois sentidos
  • Evitar listar um par duas vezes ou listar números perfeitos

Problema

Ver original (inglês)

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

Exemplo 1
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]].

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.