Собственными делителями числа n называют все его положительные делители, кроме самого n. Сравните их сумму с n: если сумма больше, число называется избыточным, если равна, совершенным, а если меньше, недостаточным. Например, собственные делители числа 12 это 1, 2, 3, 4 и 6, их сумма равна 16, поэтому 12 избыточное.
Реализуйте abundant_perfect_deficient(n).
n может достигать 10^12, поэтому перебирать все числа меньше n слишком долго. Делители идут парами d и n / d, так что достаточно перебирать d до √n.
Входные данные
n: число, которое нужно классифицировать.
Выходные данные
Верните строку "abundant" (избыточное), "perfect" (совершенное) или "deficient" (недостаточное) строчными буквами. У числа 1 нет собственных делителей (их сумма равна 0), поэтому оно недостаточное.
Ограничения
1 ≤ n ≤ 10^12
Примеры
Ввод:
n = 28
Ожидаемый вывод:
expected = "perfect"
Ввод:
long long n = 28;
Ожидаемый вывод:
std::string expected = "perfect";
Ввод:
long n = 28;
Ожидаемый вывод:
string expected = "perfect";
Пояснение
Собственные делители 1 + 2 + 4 + 7 + 14 в сумме дают 28, поэтому ответ "perfect".
Ввод:
n = 15
Ожидаемый вывод:
expected = "deficient"
Ввод:
long long n = 15;
Ожидаемый вывод:
std::string expected = "deficient";
Ввод:
long n = 15;
Ожидаемый вывод:
string expected = "deficient";
Пояснение
Собственные делители 1 + 3 + 5 в сумме дают 9, а это меньше 15, поэтому ответ "deficient".
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Если d делит n, то n / d тоже делит n; перебирайте d, только пока d × d ≤ n.
Подсказка 2
Если d × d = n, прибавьте d один раз, а не два.
Подсказка 3
Не забудьте исключить из суммы само n и отдельно обработайте n = 1.
Ожидаемая сложность
время O(√n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.