Problème
Notons s(n) la somme des diviseurs stricts de n (ses diviseurs autres que n lui-même). Deux nombres distincts a et b forment un couple de nombres amicaux quand s(a) = b et s(b) = a. Le plus petit couple est 220 et 284, car s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 et s(284) = 1 + 2 + 4 + 71 + 142 = 220.
Implémentez amicable_pair(limit).
Calculer s(n) séparément pour chaque n jusqu'à limit est lent. Un crible fonctionne mieux : pour chaque d, ajoutez d à chaque multiple de d supérieur à d.
Entrée
limit : la plus grande valeur autorisée pour chacun des deux nombres d'un couple.
Sortie
Renvoyez une liste de couples [a, b] avec a < b ≤ limit, triés par a croissant. Un couple n'est retenu que si ses deux nombres sont au plus égaux à limit. Les nombres parfaits (pour lesquels s(n) = n) ne forment pas de couple. S'il n'y en a aucun, renvoyez une liste vide.
Contraintes
1 ≤ limit ≤ 200 000
Exemples
Entrée :
limit = 1500
Sortie attendue :
expected = [
[220, 284],
[1184, 1210]
]
Entrée :
long long limit = 1500;
Sortie attendue :
std::vector<std::vector<long long>> expected = {
{220, 284},
{1184, 1210}
};
Entrée :
long limit = 1500;
Sortie attendue :
long[][] expected = new long[][] {
new long[] {220, 284},
new long[] {1184, 1210}
};
Explication
s(220) = 284 et s(284) = 220, ainsi que s(1184) = 1210 et s(1210) = 1184. Les deux couples tiennent sous 1500 : [[220, 284], [1184, 1210]].
Entrée :
limit = 250
Sortie attendue :
expected = []
Entrée :
long long limit = 250;
Sortie attendue :
std::vector<std::vector<long long>> expected = {};
Entrée :
long limit = 250;
Sortie attendue :
long[][] expected = new long[][] {};
Explication
220 ne dépasse pas 250, mais son partenaire 284 si, donc aucun couple ne convient : [].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Pour chaque d de 1 à limit / 2, ajoutez d aux sommes de 2d, 3d, 4d, et ainsi de suite.
Indice 2
Pour chaque a, notez b la somme de ses diviseurs et vérifiez que b est dans l'intervalle et que la somme des diviseurs de b vaut a.
Indice 3
Exiger a < b permet de lister chaque couple une seule fois et d'écarter les nombres parfaits.
Complexité attendue
temps O(limit log limit), espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.