문제
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 ≤ n인 동안만 반복하세요.
힌트 2
d × d = n이면 d는 두 번이 아니라 한 번만 더하세요.
힌트 3
n 자신은 합에서 빼야 하고, n = 1은 따로 처리하세요.
예상 복잡도
시간 O(√n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.