โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำนวนคู่มิตร

หาจำนวนคู่มิตรทุกคู่ที่ทั้งสองจำนวนมีค่าไม่เกินขีดจำกัดที่กำหนด

สิ่งที่คุณจะได้เรียนรู้

  • สร้างตารางผลรวมตัวหารแท้ของทุกจำนวนจนถึงขีดจำกัด
  • ตรวจเงื่อนไขของคู่ทั้งสองทิศทาง
  • ไม่ใส่คู่เดิมซ้ำและไม่ใส่จำนวนสมบูรณ์

โจทย์

ให้ 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

ตัวอย่าง

ตัวอย่างที่ 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 และ s(284) = 220 ส่วน s(1184) = 1210 และ s(1210) = 1184 ทั้งสองคู่ไม่เกิน 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 ไม่เกิน 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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก