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

ผลรวมของตัวหารแท้

หาผลรวมของตัวหารทุกตัวของ n ที่น้อยกว่า n

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

  • หาตัวหารทีละคู่
  • หยุดลูปที่รากที่สอง
  • ไม่นับตัวหารที่เป็นรากที่สองซ้ำสองครั้ง

โจทย์

ตัวหารแท้ของ 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 12

ผลลัพธ์ที่คาดหวัง:
expected = 16
อินพุต:
long long n = 12;

ผลลัพธ์ที่คาดหวัง:
long long expected = 16;
อินพุต:
long n = 12;

ผลลัพธ์ที่คาดหวัง:
long expected = 16;

คำอธิบาย

1 + 2 + 3 + 4 + 6 = 16

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

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

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

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

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

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