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