Đề bài
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ụ
Đầ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.
Đầ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.