보통 0명 해결 정답률 0%

Amicable Pair

List every amicable pair whose two numbers are both at most a limit.

배우게 될 내용

  • Build a table of proper-divisor sums for every number up to a limit
  • Check a pair condition in both directions
  • Avoid listing a pair twice or listing perfect numbers

문제

번역본 보기

Let s(n) be the sum of the proper divisors of n (its divisors other than n itself). Two different numbers a and b form an amicable pair when s(a) = b and s(b) = a. The smallest pair is 220 and 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 and s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Implement amicable_pair(limit).

Computing s(n) for every n up to limit one at a time is slow. A sieve works better: for every d, add d to each multiple of d above d.

Input

limit: The largest number either member of a pair may have.

Output

Return a list of pairs [a, b] with a < b ≤ limit, sorted by a in ascending order. A pair is included only if both numbers are at most limit. Perfect numbers (where s(n) = n) are not pairs. If there are none, return an empty list.

제약 조건

1 ≤ limit ≤ 200,000

예시

예시 1
입력:
limit = 1500

예상 출력:
expected = [
    [220, 284],
    [1184, 1210]
]
입력:
long long limit = 1500;

예상 출력:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
입력:
long limit = 1500;

예상 출력:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

설명

s(220) = 284 and s(284) = 220, and s(1184) = 1210 and s(1210) = 1184. Both pairs fit under 1500: [[220, 284], [1184, 1210]].

예시 2
입력:
limit = 250

예상 출력:
expected = []
입력:
long long limit = 250;

예상 출력:
std::vector<std::vector<long long>> expected = {};
입력:
long limit = 250;

예상 출력:
long[][] expected = new long[][] {};

설명

220 is at most 250, but its partner 284 is not, so no pair fits: [].

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

For every d from 1 to limit / 2, add d to the sums of 2d, 3d, 4d, and so on.

힌트 2

For each a, let b be its divisor sum and check that b is in range and that b's divisor sum is a.

힌트 3

Requiring a < b lists each pair once and skips perfect numbers.

예상 복잡도

O(limit log limit) time, O(limit) extra space

참고 자료

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

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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