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