โจทย์
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
ตัวอย่าง
อินพุต:
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]].
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน