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

จำนวนเหลือเฟือ จำนวนสมบูรณ์ หรือจำนวนพร่อง

จำแนกจำนวนว่าเป็นจำนวนเหลือเฟือ จำนวนสมบูรณ์ หรือจำนวนพร่อง จากผลรวมของตัวหารแท้

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

  • หาผลรวมตัวหารแท้ในเวลา O(√n)
  • ไม่นับตัวหารที่เป็นรากที่สองซ้ำสองครั้ง
  • คืนค่าป้ายกำกับหนึ่งในสามแบบจากการเปรียบเทียบ

โจทย์

ตัวหารแท้ของ n คือตัวหารบวกทั้งหมดของมัน ยกเว้นตัว n เอง ให้นำผลรวมของตัวหารแท้มาเทียบกับ n ถ้าผลรวมมากกว่า จำนวนนั้นเป็น จำนวนเหลือเฟือ (abundant) ถ้าเท่ากันเป็น จำนวนสมบูรณ์ (perfect) และถ้าน้อยกว่าเป็น จำนวนพร่อง (deficient) เช่น ตัวหารแท้ของ 12 คือ 1, 2, 3, 4 และ 6 ซึ่งรวมกันได้ 16 ดังนั้น 12 เป็นจำนวนเหลือเฟือ

จงเขียน abundant_perfect_deficient(n)

n อาจมีค่าได้ถึง 10^12 การไล่ตรวจทุกจำนวนที่น้อยกว่า n จึงช้าเกินไปมาก ตัวหารจะมาเป็นคู่เสมอคือ d กับ n / d คุณจึงลอง d แค่ถึง √n ก็พอ

อินพุต

n: จำนวนที่ต้องการจำแนก

เอาต์พุต

คืนค่าสตริง "abundant", "perfect" หรือ "deficient" เป็นตัวพิมพ์เล็ก 1 ไม่มีตัวหารแท้ (ผลรวมเป็น 0) จึงเป็นจำนวนพร่อง

เงื่อนไข

1 ≤ n ≤ 10^12

ตัวอย่าง

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

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

ผลลัพธ์ที่คาดหวัง:
std::string expected = "perfect";
อินพุต:
long n = 28;

ผลลัพธ์ที่คาดหวัง:
string expected = "perfect";

คำอธิบาย

ตัวหารแท้ 1 + 2 + 4 + 7 + 14 รวมกันได้ 28 คำตอบจึงเป็น "perfect"

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

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

ผลลัพธ์ที่คาดหวัง:
std::string expected = "deficient";
อินพุต:
long n = 15;

ผลลัพธ์ที่คาดหวัง:
string expected = "deficient";

คำอธิบาย

ตัวหารแท้ 1 + 3 + 5 รวมกันได้ 9 ซึ่งน้อยกว่า 15 คำตอบจึงเป็น "deficient"

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ถ้า d หาร n ลงตัว n / d ก็หาร n ลงตัวด้วย ให้วนลูป d เฉพาะขณะที่ d × d ≤ n

คำใบ้ 2

เมื่อ d × d = n ให้บวก d เพียงครั้งเดียว ไม่ใช่สองครั้ง

คำใบ้ 3

อย่าลืมไม่นับตัว n เองในผลรวม และจัดการกรณี n = 1 แยกต่างหาก

ความซับซ้อนที่คาดหวัง

เวลา O(√n), หน่วยความจำเพิ่ม O(1)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

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

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

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

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