Tous les défis
Moyen 0 résolus 0 % de réussite

Paires de nombres pentagonaux

Compter les paires de nombres pentagonaux dont la somme est elle aussi pentagonale.

Ce que vous allez apprendre

  • Générer les nombres pentagonaux
  • Tester l'appartenance à l'aide d'une formule
  • Compter des paires avec une double boucle

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.