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