Problema
Os divisores próprios de n são os seus divisores positivos, exceto o próprio n. Compare a soma deles com n: se a soma for maior, o número é abundante; se for igual, o número é perfeito; e se for menor, o número é deficiente. Por exemplo, os divisores próprios de 12 são 1, 2, 3, 4 e 6, que somam 16, então 12 é abundante.
Implemente abundant_perfect_deficient(n).
n pode chegar a 10^12, então testar todos os números menores que n é lento demais. Os divisores aparecem em pares d e n / d, por isso basta testar d até √n.
Entrada
n: o número a ser classificado.
Saída
Retorne a string "abundant", "perfect" ou "deficient", em minúsculas. 1 não tem divisores próprios (soma 0), então é deficiente.
Restrições
1 ≤ n ≤ 10^12
Exemplos
Entrada:
n = 28
Saída esperada:
expected = "perfect"
Entrada:
long long n = 28;
Saída esperada:
std::string expected = "perfect";
Entrada:
long n = 28;
Saída esperada:
string expected = "perfect";
Explicação
Os divisores próprios 1 + 2 + 4 + 7 + 14 somam 28, então a resposta é "perfect".
Entrada:
n = 15
Saída esperada:
expected = "deficient"
Entrada:
long long n = 15;
Saída esperada:
std::string expected = "deficient";
Entrada:
long n = 15;
Saída esperada:
string expected = "deficient";
Explicação
Os divisores próprios 1 + 3 + 5 somam 9, que é menor que 15, então a resposta é "deficient".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Se d divide n, então n / d também divide; faça o laço em d só enquanto d × d ≤ n.
Dica 2
Quando d × d = n, some d uma vez só, e não duas.
Dica 3
Lembre-se de deixar o próprio n fora da soma e trate n = 1 separadamente.
Complexidade esperada
tempo O(√n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.