Все задачи
Средне Решено: 0 Процент решений: 0%

Треугольное число с большим количеством делителей

Найдите первое треугольное число, у которого не меньше d делителей.

Чему вы научитесь

  • Считать делители по разложению на простые множители
  • Использовать формулу треугольных чисел
  • Разбивать произведение на взаимно простые множители

Условие

Треугольные числа считают точки в треугольнике из рядов по 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

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.