Problem
Die Fünfeckszahlen sind P(k) = k(3k − 1) / 2, also 1, 5, 12, 22, 35, 51, 70, ... Manche Paare ergeben zusammen wieder eine Fünfeckszahl, etwa P(4) + P(7) = 22 + 70 = 92 = P(8). Zähle die Paare j < k ≤ n, für die P(j) + P(k) eine Fünfeckszahl ist. Ein schneller Test hilft: x ist genau dann eine Fünfeckszahl, wenn 24x + 1 eine Quadratzahl s² mit s % 6 = 5 ist.
Implementiere pentagonal_pair(n).
Eingabe
n: Der größte Index k, der verwendet wird.
Ausgabe
Gib die Anzahl der Paare (j, k) mit 1 ≤ j < k ≤ n zurück, für die P(j) + P(k) eine Fünfeckszahl ist.
Einschränkungen
1 ≤ n ≤ 1000
Beispiele
Eingabe:
n = 7
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 7;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 7;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
Von den 21 Paaren bis k = 7 ergibt nur P(4) + P(7) = 92 = P(8) eine Fünfeckszahl, also lautet die Antwort 1.
Eingabe:
n = 1
Erwartete Ausgabe:
expected = 0
Eingabe:
long long n = 1;
Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long n = 1;
Erwartete Ausgabe:
long expected = 0;
Erläuterung
Es gibt kein Paar mit j < k ≤ 1, also lautet die Antwort 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
P(k) = k(3k − 1) / 2.
Hinweis 2
Prüfe mit einer ganzzahligen Quadratwurzel, ob 24x + 1 eine Quadratzahl ist, und dann die Wurzel modulo 6.
Hinweis 3
Gezählt werden nur Paare mit j < k.
Erwartete Komplexität
Zeit O(n²), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.