모든 챌린지
쉬움 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 ≤ n인 동안만 반복하세요.

힌트 2

d × d = n이면 d는 두 번이 아니라 한 번만 더하세요.

힌트 3

n 자신은 합에서 빼야 하고, n = 1은 따로 처리하세요.

예상 복잡도

시간 O(√n), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.