Problème
Les nombres pentagonaux sont P(k) = k(3k − 1) / 2 : 1, 5, 12, 22, 35, 51, 70, ... Certaines paires ont pour somme un autre nombre pentagonal, comme P(4) + P(7) = 22 + 70 = 92 = P(8). Comptez les paires j < k ≤ n pour lesquelles P(j) + P(k) est pentagonal. Un test rapide aide : x est pentagonal exactement lorsque 24x + 1 est un carré parfait s² avec s % 6 = 5.
Implémentez pentagonal_pair(n).
Entrée
n : le plus grand indice k à utiliser.
Sortie
Renvoyez le nombre de paires (j, k) telles que 1 ≤ j < k ≤ n et P(j) + P(k) est pentagonal.
Contraintes
1 ≤ n ≤ 1000
Exemples
Entrée :
n = 7
Sortie attendue :
expected = 1
Entrée :
long long n = 7;
Sortie attendue :
long long expected = 1;
Entrée :
long n = 7;
Sortie attendue :
long expected = 1;
Explication
Parmi les 21 paires jusqu'à k = 7, seule P(4) + P(7) = 92 = P(8) est pentagonale, donc la réponse est 1.
Entrée :
n = 1
Sortie attendue :
expected = 0
Entrée :
long long n = 1;
Sortie attendue :
long long expected = 0;
Entrée :
long n = 1;
Sortie attendue :
long expected = 0;
Explication
Il n'existe aucune paire avec j < k ≤ 1, donc la réponse est 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
P(k) = k(3k − 1) / 2.
Indice 2
Vérifiez si 24x + 1 est un carré parfait à l'aide d'une racine carrée entière, puis vérifiez la racine modulo 6.
Indice 3
Seules les paires avec j < k sont comptées.
Complexité attendue
temps O(n²), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.