Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Highly Divisible Triangular Number

Find the first triangular number that has at least d divisors.

Das lernst du

  • Count divisors from a prime factorization
  • Use the formula for triangular numbers
  • Split a product of coprime factors

Problem

Übersetzung anzeigen

Triangular numbers count the dots in a triangle of rows 1, 2, 3, ...: T(1) = 1, T(2) = 3, T(3) = 6, and T(k) = k(k + 1) / 2. Walk through them in order and stop at the first one with at least d positive divisors (1 and the number itself count).

Implement highly_divisible_triangular(d).

Counting divisors one by one is too slow for the larger cases. Factor the number instead: if n = p^a × q^b × ..., it has (a + 1)(b + 1)... divisors. Since k and k + 1 share no factor, you can factor them separately.

Input

d: The number of divisors needed.

Output

Return the first triangular number with at least d divisors.

Einschränkungen

1 ≤ d ≤ 300

Beispiele

Beispiel 1
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 has one divisor and 3 has two, but 6 has four (1, 2, 3, 6), so the answer is 6.

Beispiel 2
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 has six divisors and 36 = 2² × 3² has 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), so the answer is 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, and k and k + 1 have no common factor.

Hinweis 2

Halve whichever of k and k + 1 is even, then count the divisors of each part.

Hinweis 3

The divisor count of a product of coprime numbers is the product of their counts.

Erwartete Komplexität

O(K √K) time for K triangular numbers tried, O(1) extra space

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.