Problem
Dreieckszahlen geben an, wie viele Punkte ein Dreieck mit den Zeilenlängen 1, 2, 3, ... hat: T(1) = 1, T(2) = 3, T(3) = 6 und allgemein T(k) = k(k + 1) / 2. Geh sie der Reihe nach durch und halte bei der ersten an, die mindestens d positive Teiler hat (1 und die Zahl selbst zählen mit).
Implementiere highly_divisible_triangular(d).
Die Teiler einzeln zu zählen ist für die größeren Fälle zu langsam. Nutze stattdessen die Primfaktorzerlegung: Ist n = p^a × q^b × ..., dann hat n genau (a + 1)(b + 1)... Teiler. Da k und k + 1 teilerfremd sind, kannst du sie getrennt zerlegen.
Eingabe
d: Die benötigte Anzahl an Teilern.
Ausgabe
Gib die erste Dreieckszahl mit mindestens d Teilern zurück.
Einschränkungen
1 ≤ d ≤ 300
Beispiele
Eingabe:
d = 4
Erwartete Ausgabe:
expected = 6
Eingabe:
long long d = 4;
Erwartete Ausgabe:
long long expected = 6;
Eingabe:
long d = 4;
Erwartete Ausgabe:
long expected = 6;
Erläuterung
1 hat einen Teiler und 3 hat zwei, aber 6 hat vier (1, 2, 3, 6), also lautet die Antwort 6.
Eingabe:
d = 9
Erwartete Ausgabe:
expected = 36
Eingabe:
long long d = 9;
Erwartete Ausgabe:
long long expected = 36;
Eingabe:
long d = 9;
Erwartete Ausgabe:
long expected = 36;
Erläuterung
28 hat sechs Teiler, 36 = 2² × 3² hat dagegen 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), also lautet die Antwort 36.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
T(k) = k(k + 1) / 2, und k und k + 1 haben keinen gemeinsamen Teiler.
Hinweis 2
Halbiere die gerade der beiden Zahlen k und k + 1 und zähle dann die Teiler jedes Teils.
Hinweis 3
Die Teileranzahl eines Produkts teilerfremder Zahlen ist das Produkt ihrer Teileranzahlen.
Erwartete Komplexität
Zeit O(K √K) bei K geprüften Dreieckszahlen, zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.