Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Amicable Pair

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

Bạn sẽ học được gì

  • 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

Đề bài

Xem bản dịch

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.

Ràng buộc

1 ≤ limit ≤ 200,000

Ví dụ

Ví dụ 1
Đầu vào:
limit = 1500

Kết quả mong đợi:
expected = [
    [220, 284],
    [1184, 1210]
]
Đầu vào:
long long limit = 1500;

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Đầu vào:
long limit = 1500;

Kết quả mong đợi:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Giải thích

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

Ví dụ 2
Đầu vào:
limit = 250

Kết quả mong đợi:
expected = []
Đầu vào:
long long limit = 250;

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {};
Đầu vào:
long limit = 250;

Kết quả mong đợi:
long[][] expected = new long[][] {};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 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.

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.