โจทย์
ตัวหารแท้ของ n คือตัวหารที่เป็นบวกทั้งหมดยกเว้นตัว n เอง เช่น ตัวหารแท้ของ 12 ได้แก่ 1, 2, 3, 4 และ 6 ผลรวมของตัวหารแท้ (บางครั้งเรียกว่า aliquot sum) ใช้บอกได้ว่าจำนวนนั้นเป็นจำนวนสมบูรณ์ จำนวนเกิน หรือจำนวนพร่อง ตัวหารจะมาเป็นคู่ d กับ n / d เสมอ จึงต้องลองค่า d ไปจนถึงรากที่สองของ n เท่านั้น
จงเขียนฟังก์ชัน sum_of_proper_divisors(n)
อินพุต
n: จำนวนเต็มบวก
เอาต์พุต
คืนค่าผลรวมของตัวหารบวกทุกตัวของ n ที่น้อยกว่า n กรณี n = 1 ไม่มีตัวหารแท้เลย ให้คืนค่า 0
เงื่อนไข
1 ≤ n ≤ 10^12
ตัวอย่าง
อินพุต:
n = 12
ผลลัพธ์ที่คาดหวัง:
expected = 16
อินพุต:
long long n = 12;
ผลลัพธ์ที่คาดหวัง:
long long expected = 16;
อินพุต:
long n = 12;
ผลลัพธ์ที่คาดหวัง:
long expected = 16;
คำอธิบาย
1 + 2 + 3 + 4 + 6 = 16
อินพุต:
n = 28
ผลลัพธ์ที่คาดหวัง:
expected = 28
อินพุต:
long long n = 28;
ผลลัพธ์ที่คาดหวัง:
long long expected = 28;
อินพุต:
long n = 28;
ผลลัพธ์ที่คาดหวัง:
long expected = 28;
คำอธิบาย
1 + 2 + 4 + 7 + 14 = 28 ดังนั้น 28 เป็นจำนวนสมบูรณ์
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ถ้า d หาร n ลงตัว n / d ก็หาร n ลงตัวด้วย
คำใบ้ 2
ลอง d ไปจนถึงรากที่สองของ n เท่านั้น แล้วบวกทั้งสองตัวของแต่ละคู่
คำใบ้ 3
อย่านับ n เอง และถ้า n เป็นกำลังสองสมบูรณ์ ให้บวกรากที่สองเพียงครั้งเดียว
ความซับซ้อนที่คาดหวัง
เวลา O(sqrt n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน