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