Tutte le sfide
Media 0 risolte 0% di accettazione

Numeri amicabili

Elenca tutte le coppie di numeri amicabili in cui entrambi i numeri non superano un certo limite.

Cosa imparerai

  • Costruire una tabella con la somma dei divisori propri di ogni numero fino a un limite
  • Verificare una condizione di coppia in entrambe le direzioni
  • Evitare di elencare due volte una coppia o di includere i numeri perfetti

Problema

Sia s(n) la somma dei divisori propri di n (cioè dei suoi divisori diversi da n stesso). Due numeri diversi a e b formano una coppia di numeri amicabili quando s(a) = b e s(b) = a. La coppia più piccola è 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.

Implementa amicable_pair(limit).

Calcolare s(n) uno alla volta per ogni n fino a limit è lento. Conviene usare un crivello: per ogni d, aggiungi d a ciascun multiplo di d maggiore di d.

Input

limit: il valore massimo che può avere ciascuno dei due numeri della coppia.

Output

Restituisci una lista di coppie [a, b] con a < b ≤ limit, ordinate per a in ordine crescente. Una coppia compare solo se entrambi i numeri non superano limit. I numeri perfetti (per cui s(n) = n) non formano coppie. Se non ci sono coppie, restituisci una lista vuota.

Vincoli

1 ≤ limit ≤ 200 000

Esempi

Esempio 1
Input:
limit = 1500

Output atteso:
expected = [
    [220, 284],
    [1184, 1210]
]
Input:
long long limit = 1500;

Output atteso:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Input:
long limit = 1500;

Output atteso:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Spiegazione

s(220) = 284 e s(284) = 220, e s(1184) = 1210 e s(1210) = 1184. Entrambe le coppie stanno sotto 1500: [[220, 284], [1184, 1210]].

Esempio 2
Input:
limit = 250

Output atteso:
expected = []
Input:
long long limit = 250;

Output atteso:
std::vector<std::vector<long long>> expected = {};
Input:
long limit = 250;

Output atteso:
long[][] expected = new long[][] {};

Spiegazione

220 non supera 250, ma il suo compagno 284 sì, quindi nessuna coppia rientra nel limite: [].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Per ogni d da 1 a limit / 2, aggiungi d alle somme di 2d, 3d, 4d e così via.

Suggerimento 2

Per ogni a, sia b la somma dei suoi divisori; controlla che b rientri nel limite e che la somma dei divisori di b sia a.

Suggerimento 3

Imporre a < b fa comparire ogni coppia una sola volta ed esclude i numeri perfetti.

Complessità attesa

tempo O(limit log limit), spazio aggiuntivo O(limit)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.