Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Highly Divisible Triangular Number

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

1 ≤ d ≤ 300

Ví dụ

Ví dụ 1
Đầu vào:
d = 4

Kết quả mong đợi:
expected = 6
Đầu vào:
long long d = 4;

Kết quả mong đợi:
long long expected = 6;
Đầu vào:
long d = 4;

Kết quả mong đợi:
long expected = 6;

Giải thích

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

Ví dụ 2
Đầu vào:
d = 9

Kết quả mong đợi:
expected = 36
Đầu vào:
long long d = 9;

Kết quả mong đợi:
long long expected = 36;
Đầu vào:
long d = 9;

Kết quả mong đợi:
long expected = 36;

Giải thích

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.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.