Đề bài
Số tam giác là số chấm trong một hình tam giác có các hàng 1, 2, 3, ...: T(1) = 1, T(2) = 3, T(3) = 6, và T(k) = k(k + 1) / 2. Hãy duyệt các số tam giác theo thứ tự và dừng lại ở số đầu tiên có ít nhất d ước dương (tính cả 1 và chính nó).
Hãy viết highly_divisible_triangular(d).
Đếm ước bằng cách thử từng số sẽ quá chậm với các test lớn. Thay vào đó, hãy phân tích thừa số nguyên tố: nếu n = p^a × q^b × ..., thì n có (a + 1)(b + 1)... ước. Vì k và k + 1 không có ước chung nào, bạn có thể phân tích riêng từng số.
Đầu vào
d: Số ước cần đạt.
Đầu ra
Trả về số tam giác đầu tiên có ít nhất d ước.
Ràng buộc
1 ≤ d ≤ 300
Ví dụ
Đầ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 có một ước và 3 có hai ước, còn 6 có bốn ước (1, 2, 3, 6), nên đáp án là 6.
Đầ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 có sáu ước, còn 36 = 2² × 3² có 3 × 3 = 9 ước (1, 2, 3, 4, 6, 9, 12, 18, 36), nên đáp án là 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, và k với k + 1 không có ước chung.
Gợi ý 2
Chia đôi số chẵn trong hai số k và k + 1, rồi đếm số ước của từng phần.
Gợi ý 3
Số ước của tích hai số nguyên tố cùng nhau bằng tích số ước của từng số.
Độ phức tạp mong đợi
thời gian O(K √K) với K là số số tam giác đã thử, bộ nhớ phụ O(1)
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.