문제
진약수(자기 자신을 뺀 모든 약수)의 합이 그 수보다 크면 과잉수라고 합니다. 가장 작은 과잉수는 12로, 1 + 2 + 3 + 4 + 6 = 16입니다. 어떤 수는 두 과잉수의 합으로 나타낼 수 있고(24 = 12 + 12처럼 같은 수를 두 번 써도 됩니다) 어떤 수는 그럴 수 없습니다. 1부터 limit까지의 양의 정수 중 나타낼 수 없는 수를 모두 더하세요.
non_abundant_sums(limit) 함수를 구현하세요.
체를 이용해 모든 수의 약수 합을 한 번에 구하고, 과잉수 목록을 만든 다음, 한계값을 넘지 않는 두 과잉수의 합을 모두 표시하세요.
입력
limit: 확인할 가장 큰 수입니다.
출력
1 ≤ n ≤ limit이면서 두 과잉수의 합이 아닌 모든 n의 합을 반환합니다.
제약 조건
1 ≤ limit ≤ 10,000
예시
입력:
limit = 23
예상 출력:
expected = 276
입력:
long long limit = 23;
예상 출력:
long long expected = 276;
입력:
long limit = 23;
예상 출력:
long expected = 276;
설명
두 과잉수를 더해 23 이하가 되는 경우는 없으므로 모든 수가 해당됩니다. 1 + 2 + ... + 23 = 276입니다.
입력:
limit = 30
예상 출력:
expected = 411
입력:
long long limit = 30;
예상 출력:
long long expected = 411;
입력:
long limit = 30;
예상 출력:
long expected = 411;
설명
24 = 12 + 12와 30 = 12 + 18은 빠지므로 답은 465 − 24 − 30 = 411입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 i에 대해 2i, 3i, 4i, ...의 약수 합에 i를 더하세요.
힌트 2
과잉수를 오름차순으로 모으세요.
힌트 3
a ≤ b인 각 쌍에서 a + b가 한계값을 넘으면 안쪽 반복을 멈추세요.
예상 복잡도
시간 O(limit log limit + A²) (A는 과잉수의 개수), 추가 공간 O(limit)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.