모든 챌린지
어려움 0명 해결 정답률 0%

두 과잉수의 합으로 나타낼 수 없는 수

한계값 이하에서 두 과잉수의 합으로 나타낼 수 없는 수를 모두 더합니다.

배우게 될 내용

  • 체로 구간 전체의 약수 합을 계산할 수 있다
  • 불리언 배열로 만들 수 있는 합을 표시할 수 있다
  • 합이 한계값을 넘으면 이중 반복을 일찍 끝낼 수 있다

문제

원문 보기 (영어)

진약수(자기 자신을 뺀 모든 약수)의 합이 그 수보다 크면 과잉수라고 합니다. 가장 작은 과잉수는 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

예시

예시 1
입력:
limit = 23

예상 출력:
expected = 276
입력:
long long limit = 23;

예상 출력:
long long expected = 276;
입력:
long limit = 23;

예상 출력:
long expected = 276;

설명

두 과잉수를 더해 23 이하가 되는 경우는 없으므로 모든 수가 해당됩니다. 1 + 2 + ... + 23 = 276입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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