Все задачи
Легко Решено: 0 Процент решений: 0%

Избыточное, совершенное или недостаточное число

Определите по сумме собственных делителей, является ли число избыточным, совершенным или недостаточным.

Чему вы научитесь

  • Находить сумму собственных делителей за время O(√n)
  • Не учитывать дважды делитель, равный корню
  • Возвращать одну из трёх меток по результату сравнения

Условие

Собственными делителями числа 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

Примеры

Пример 1
Ввод:
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".

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.