Đề bài
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ụ
Đầ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]].
Đầ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.