Tutte le sfide
Media 0 risolte 0% di accettazione

Coppie di numeri pentagonali

Conta le coppie di numeri pentagonali la cui somma è anch'essa un numero pentagonale.

Cosa imparerai

  • Generare i numeri pentagonali
  • Verificare l'appartenenza con una formula
  • Contare le coppie con un doppio ciclo

Problema

I numeri pentagonali sono P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Alcune coppie hanno per somma un altro numero pentagonale, come P(4) + P(7) = 22 + 70 = 92 = P(8). Conta le coppie j < k ≤ n per cui P(j) + P(k) è pentagonale. Un test veloce aiuta: x è pentagonale esattamente quando 24x + 1 è un quadrato perfetto s² con s % 6 = 5.

Implementa pentagonal_pair(n).

Input

n: l'indice k più grande da usare.

Output

Restituisci il numero di coppie (j, k) con 1 ≤ j < k ≤ n e P(j) + P(k) pentagonale.

Vincoli

1 ≤ n ≤ 1000

Esempi

Esempio 1
Input:
n = 7

Output atteso:
expected = 1
Input:
long long n = 7;

Output atteso:
long long expected = 1;
Input:
long n = 7;

Output atteso:
long expected = 1;

Spiegazione

Delle 21 coppie fino a k = 7, solo P(4) + P(7) = 92 = P(8) è pentagonale, quindi la risposta è 1.

Esempio 2
Input:
n = 1

Output atteso:
expected = 0
Input:
long long n = 1;

Output atteso:
long long expected = 0;
Input:
long n = 1;

Output atteso:
long expected = 0;

Spiegazione

Non esiste nessuna coppia con j < k ≤ 1, quindi la risposta è 0.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

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

Suggerimento 2

Verifica se 24x + 1 è un quadrato perfetto con una radice quadrata intera, poi controlla la radice modulo 6.

Suggerimento 3

Si contano solo le coppie con j < k.

Complessità attesa

tempo O(n²), spazio aggiuntivo O(n)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.