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

Highly Divisible Triangular Number

Find the first triangular number that has at least d divisors.

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

  • Count divisors from a prime factorization
  • Use the formula for triangular numbers
  • Split a product of coprime factors

โจทย์

ดูฉบับแปล

Triangular numbers count the dots in a triangle of rows 1, 2, 3, ...: T(1) = 1, T(2) = 3, T(3) = 6, and T(k) = k(k + 1) / 2. Walk through them in order and stop at the first one with at least d positive divisors (1 and the number itself count).

Implement highly_divisible_triangular(d).

Counting divisors one by one is too slow for the larger cases. Factor the number instead: if n = p^a × q^b × ..., it has (a + 1)(b + 1)... divisors. Since k and k + 1 share no factor, you can factor them separately.

Input

d: The number of divisors needed.

Output

Return the first triangular number with at least d divisors.

เงื่อนไข

1 ≤ d ≤ 300

ตัวอย่าง

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

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

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

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

คำอธิบาย

1 has one divisor and 3 has two, but 6 has four (1, 2, 3, 6), so the answer is 6.

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

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

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

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

คำอธิบาย

28 has six divisors and 36 = 2² × 3² has 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), so the answer is 36.

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

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

คำใบ้ 1

T(k) = k(k + 1) / 2, and k and k + 1 have no common factor.

คำใบ้ 2

Halve whichever of k and k + 1 is even, then count the divisors of each part.

คำใบ้ 3

The divisor count of a product of coprime numbers is the product of their counts.

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

O(K √K) time for K triangular numbers tried, O(1) extra space

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

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

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

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

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

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

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