โจทย์
จำนวนหนึ่งจะเป็นจำนวนเกิน (abundant number) เมื่อผลรวมของตัวหารแท้ (ตัวหารทั้งหมดยกเว้นตัวมันเอง) มากกว่าตัวมันเอง จำนวนเกินที่น้อยที่สุดคือ 12 เพราะ 1 + 2 + 3 + 4 + 6 = 16 บางจำนวนเขียนเป็นผลบวกของจำนวนเกินสองจำนวนได้ (ใช้จำนวนเดียวกันซ้ำสองครั้งก็ได้ เช่น 24 = 12 + 12) และบางจำนวนก็เขียนไม่ได้ ให้หาผลรวมของจำนวนเต็มบวกทุกตัวตั้งแต่ 1 ถึง limit ที่เขียนไม่ได้
จงเขียนฟังก์ชัน non_abundant_sums(limit)
ให้หาผลรวมตัวหารของทุกจำนวนพร้อมกันด้วยตะแกรง ทำรายการจำนวนเกิน แล้วทำเครื่องหมายผลบวกของทุกคู่ที่ยังไม่เกิน limit
อินพุต
limit: จำนวนที่มากที่สุดที่ต้องตรวจสอบ
เอาต์พุต
คืนค่าผลรวมของ n ทุกตัวที่ 1 ≤ n ≤ limit และไม่เป็นผลบวกของจำนวนเกินสองจำนวน
เงื่อนไข
1 ≤ limit ≤ 10,000
ตัวอย่าง
อินพุต:
limit = 23
ผลลัพธ์ที่คาดหวัง:
expected = 276
อินพุต:
long long limit = 23;
ผลลัพธ์ที่คาดหวัง:
long long expected = 276;
อินพุต:
long limit = 23;
ผลลัพธ์ที่คาดหวัง:
long expected = 276;
คำอธิบาย
ไม่มีจำนวนเกินสองจำนวนใดที่บวกกันแล้วได้ไม่เกิน 23 ทุกจำนวนจึงถูกนับ ได้ 1 + 2 + ... + 23 = 276
อินพุต:
limit = 30
ผลลัพธ์ที่คาดหวัง:
expected = 411
อินพุต:
long long limit = 30;
ผลลัพธ์ที่คาดหวัง:
long long expected = 411;
อินพุต:
long limit = 30;
ผลลัพธ์ที่คาดหวัง:
long expected = 411;
คำอธิบาย
24 = 12 + 12 และ 30 = 12 + 18 ถูกตัดออก คำตอบจึงเป็น 465 − 24 − 30 = 411
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สำหรับแต่ละ i ให้บวก i เข้าไปในผลรวมตัวหารของ 2i, 3i, 4i, ...
คำใบ้ 2
เก็บจำนวนเกินไว้เรียงจากน้อยไปมาก
คำใบ้ 3
สำหรับแต่ละคู่ a ≤ b ให้หยุดลูปในทันทีที่ a + b เกินขีดจำกัด
ความซับซ้อนที่คาดหวัง
เวลา O(limit log limit + A²) โดย A คือจำนวนของจำนวนเกิน, หน่วยความจำเพิ่ม O(limit)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน