Треугольные числа считают точки в треугольнике из рядов по 1, 2, 3, ... точки: T(1) = 1, T(2) = 3, T(3) = 6, и вообще T(k) = k(k + 1) / 2. Перебирайте их по порядку и остановитесь на первом, у которого не меньше d положительных делителей (1 и само число тоже считаются).
Реализуйте highly_divisible_triangular(d).
На больших тестах подсчёт делителей перебором работает слишком медленно. Вместо этого разложите число на простые множители: если n = p^a × q^b × ..., то у него (a + 1)(b + 1)... делителей. Так как k и k + 1 взаимно просты, их можно раскладывать по отдельности.
Входные данные
d: требуемое количество делителей.
Выходные данные
Верните первое треугольное число, у которого не меньше d делителей.
Ограничения
1 ≤ d ≤ 300
Примеры
Ввод:
d = 4
Ожидаемый вывод:
expected = 6
Ввод:
long long d = 4;
Ожидаемый вывод:
long long expected = 6;
Ввод:
long d = 4;
Ожидаемый вывод:
long expected = 6;
Пояснение
У 1 один делитель, у 3 два, а у 6 четыре (1, 2, 3, 6), поэтому ответ 6.
Ввод:
d = 9
Ожидаемый вывод:
expected = 36
Ввод:
long long d = 9;
Ожидаемый вывод:
long long expected = 36;
Ввод:
long d = 9;
Ожидаемый вывод:
long expected = 36;
Пояснение
У 28 шесть делителей, а у 36 = 2² × 3² их 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), поэтому ответ 36.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
T(k) = k(k + 1) / 2, а у k и k + 1 нет общих множителей.
Подсказка 2
Разделите пополам то из чисел k и k + 1, которое чётное, а затем посчитайте делители каждой части.
Подсказка 3
Количество делителей произведения взаимно простых чисел равно произведению их количеств делителей.
Ожидаемая сложность
время O(K √K) для K проверенных треугольных чисел, доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.