Problema
Os números pentagonais são P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Alguns pares somam outro número pentagonal, como P(4) + P(7) = 22 + 70 = 92 = P(8). Conte os pares j < k ≤ n para os quais P(j) + P(k) é pentagonal. Um teste rápido ajuda: x é pentagonal exatamente quando 24x + 1 é um quadrado perfeito s² com s % 6 = 5.
Implemente pentagonal_pair(n).
Entrada
n: o maior índice k a usar.
Saída
Retorne a quantidade de pares (j, k) com 1 ≤ j < k ≤ n e P(j) + P(k) pentagonal.
Restrições
1 ≤ n ≤ 1000
Exemplos
Entrada:
n = 7
Saída esperada:
expected = 1
Entrada:
long long n = 7;
Saída esperada:
long long expected = 1;
Entrada:
long n = 7;
Saída esperada:
long expected = 1;
Explicação
Dos 21 pares até k = 7, só P(4) + P(7) = 92 = P(8) é pentagonal, então a resposta é 1.
Entrada:
n = 1
Saída esperada:
expected = 0
Entrada:
long long n = 1;
Saída esperada:
long long expected = 0;
Entrada:
long n = 1;
Saída esperada:
long expected = 0;
Explicação
Não existe par com j < k ≤ 1, então a resposta é 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
P(k) = k(3k − 1) / 2.
Dica 2
Verifique se 24x + 1 é um quadrado perfeito usando a raiz quadrada inteira e depois confira a raiz módulo 6.
Dica 3
Só contam os pares com j < k.
Complexidade esperada
tempo O(n²), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.