ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Sum of Proper Divisors

Add up every divisor of n that is smaller than n.

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

  • Find divisors in pairs
  • Stop the loop at the square root
  • Avoid counting a square root divisor twice

โจทย์

ดูฉบับแปล

The proper divisors of n are the positive divisors other than n itself. For 12 they are 1, 2, 3, 4 and 6. Their sum (sometimes called the aliquot sum) tells whether a number is perfect, abundant or deficient. Divisors come in pairs d and n / d, so you only need to try values of d up to the square root of n.

Implement sum_of_proper_divisors(n).

Input

n: A positive integer.

Output

Return the sum of all positive divisors of n that are less than n. For n = 1 there are none, so return 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, so 28 is a perfect number.

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

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

คำใบ้ 1

If d divides n, then n / d divides n too.

คำใบ้ 2

Only try d up to the square root of n, adding both members of each pair.

คำใบ้ 3

Leave n itself out, and add the square root only once when n is a perfect square.

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

O(sqrt n) time, O(1) extra space

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

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

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

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

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

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

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