โจทย์
ให้ s(n) เป็นผลรวมของตัวหารแท้ของ n (ตัวหารทั้งหมดยกเว้นตัว n เอง) จำนวนสองจำนวนที่ต่างกัน a และ b เป็น จำนวนคู่มิตร (amicable pair) เมื่อ s(a) = b และ s(b) = a คู่ที่เล็กที่สุดคือ 220 กับ 284 เพราะ s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 และ s(284) = 1 + 2 + 4 + 71 + 142 = 220
จงเขียน amicable_pair(limit)
การคำนวณ s(n) ทีละตัวสำหรับทุก n จนถึง limit นั้นช้า ใช้วิธีตะแกรง (sieve) จะดีกว่า คือสำหรับทุก d ให้บวก d เข้าไปในพหุคูณทุกตัวของ d ที่มากกว่า d
อินพุต
limit: ค่าที่มากที่สุดที่สมาชิกแต่ละตัวของคู่จะมีได้
เอาต์พุต
คืนค่าลิสต์ของคู่ [a, b] ที่ a < b ≤ limit เรียงตาม a จากน้อยไปมาก คู่หนึ่งจะนับก็ต่อเมื่อทั้งสองจำนวนไม่เกิน limit จำนวนสมบูรณ์ (ที่ s(n) = n) ไม่นับเป็นคู่ ถ้าไม่มีคู่เลยให้คืนค่าลิสต์ว่าง
เงื่อนไข
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 และ s(284) = 220 ส่วน s(1184) = 1210 และ s(1210) = 1184 ทั้งสองคู่ไม่เกิน 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 ไม่เกิน 250 ก็จริง แต่คู่ของมันคือ 284 เกิน จึงไม่มีคู่ใดเข้าเงื่อนไข: []
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สำหรับทุก d ตั้งแต่ 1 ถึง limit / 2 ให้บวก d เข้าไปในผลรวมของ 2d, 3d, 4d ไปเรื่อย ๆ
คำใบ้ 2
สำหรับแต่ละ a ให้ b เป็นผลรวมตัวหารของ a แล้วตรวจว่า b อยู่ในช่วงและผลรวมตัวหารของ b เท่ากับ a
คำใบ้ 3
การกำหนดให้ a < b ทำให้แต่ละคู่ถูกใส่เพียงครั้งเดียวและข้ามจำนวนสมบูรณ์ไปเอง
ความซับซ้อนที่คาดหวัง
เวลา O(limit log limit), หน่วยความจำเพิ่ม O(limit)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน