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

Пары пятиугольных чисел

Посчитайте пары пятиугольных чисел, сумма которых тоже является пятиугольным числом.

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

  • Генерировать пятиугольные числа
  • Проверять принадлежность по формуле
  • Считать пары двойным циклом

Условие

Пятиугольные числа задаются формулой P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Некоторые пары в сумме дают другое пятиугольное число, например P(4) + P(7) = 22 + 70 = 92 = P(8). Посчитайте пары j < k ≤ n, для которых P(j) + P(k) - пятиугольное число. Пригодится быстрая проверка: x пятиугольное ровно тогда, когда 24x + 1 - полный квадрат s², причём s % 6 = 5.

Реализуйте pentagonal_pair(n).

Входные данные

n: наибольший допустимый индекс k.

Выходные данные

Верните количество пар (j, k), где 1 ≤ j < k ≤ n и P(j) + P(k) - пятиугольное число.

Ограничения

1 ≤ n ≤ 1000

Примеры

Пример 1
Ввод:
n = 7

Ожидаемый вывод:
expected = 1
Ввод:
long long n = 7;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long n = 7;

Ожидаемый вывод:
long expected = 1;

Пояснение

Из 21 пары с k ≤ 7 пятиугольную сумму даёт только P(4) + P(7) = 92 = P(8), поэтому ответ 1.

Пример 2
Ввод:
n = 1

Ожидаемый вывод:
expected = 0
Ввод:
long long n = 1;

Ожидаемый вывод:
long long expected = 0;
Ввод:
long n = 1;

Ожидаемый вывод:
long expected = 0;

Пояснение

Пар с j < k ≤ 1 не бывает, поэтому ответ 0.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

P(k) = k(3k − 1) / 2.

Подсказка 2

Проверьте, является ли 24x + 1 полным квадратом, с помощью целочисленного квадратного корня, а затем проверьте корень по модулю 6.

Подсказка 3

Учитываются только пары с j < k.

Ожидаемая сложность

время O(n²), доп. память O(n)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

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

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

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

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

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