Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Paare von Fünfeckszahlen

Zähle Paare von Fünfeckszahlen, deren Summe ebenfalls eine Fünfeckszahl ist.

Das lernst du

  • Fünfeckszahlen erzeugen
  • Mit einer Formel prüfen, ob eine Zahl dazugehört
  • Paare mit einer doppelten Schleife zählen

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

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

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

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.