Problème
Les diviseurs stricts de n sont ses diviseurs positifs autres que n lui-même. Comparez leur somme à n. Si la somme est plus grande, le nombre est abondant. Si elle est égale, le nombre est parfait. Si elle est plus petite, le nombre est déficient. Par exemple, les diviseurs stricts de 12 sont 1, 2, 3, 4 et 6, dont la somme vaut 16, donc 12 est abondant.
Implémentez abundant_perfect_deficient(n).
n peut atteindre 10^12, il est donc beaucoup trop lent de tester tous les nombres inférieurs à n. Les diviseurs vont par paires d et n / d, il suffit donc d'essayer les d jusqu'à √n.
Entrée
n : le nombre à classer.
Sortie
Renvoyez la chaîne "abundant", "perfect" ou "deficient", en minuscules. 1 n'a aucun diviseur strict (somme 0), il est donc déficient.
Contraintes
1 ≤ n ≤ 10^12
Exemples
Entrée :
n = 28
Sortie attendue :
expected = "perfect"
Entrée :
long long n = 28;
Sortie attendue :
std::string expected = "perfect";
Entrée :
long n = 28;
Sortie attendue :
string expected = "perfect";
Explication
Les diviseurs stricts 1 + 2 + 4 + 7 + 14 donnent 28, donc la réponse est "perfect".
Entrée :
n = 15
Sortie attendue :
expected = "deficient"
Entrée :
long long n = 15;
Sortie attendue :
std::string expected = "deficient";
Entrée :
long n = 15;
Sortie attendue :
string expected = "deficient";
Explication
Les diviseurs stricts 1 + 3 + 5 donnent 9, ce qui est inférieur à 15, donc la réponse est "deficient".
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Si d divise n, alors n / d aussi, donc ne faites varier d que tant que d × d ≤ n.
Indice 2
Quand d × d = n, ajoutez d une seule fois, pas deux.
Indice 3
Pensez à exclure n lui-même de la somme, et traitez n = 1 à part.
Complexité attendue
temps O(√n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.