Tutte le sfide
Media 0 risolte 0% di accettazione

Numero triangolare con molti divisori

Trova il primo numero triangolare che ha almeno d divisori.

Cosa imparerai

  • Contare i divisori a partire dalla scomposizione in fattori primi
  • Usare la formula dei numeri triangolari
  • Separare un prodotto di fattori coprimi

Problema

I numeri triangolari contano i punti di un triangolo con righe di 1, 2, 3, ... punti: T(1) = 1, T(2) = 3, T(3) = 6 e in generale T(k) = k(k + 1) / 2. Scorrili in ordine e fermati al primo che ha almeno d divisori positivi (contano anche 1 e il numero stesso).

Implementa highly_divisible_triangular(d).

Contare i divisori uno per uno è troppo lento per i casi più grandi. Scomponi invece il numero in fattori primi: se n = p^a × q^b × ..., ha (a + 1)(b + 1)... divisori. Dato che k e k + 1 non hanno fattori in comune, puoi scomporli separatamente.

Input

d: il numero di divisori richiesto.

Output

Restituisci il primo numero triangolare con almeno d divisori.

Vincoli

1 ≤ d ≤ 300

Esempi

Esempio 1
Input:
d = 4

Output atteso:
expected = 6
Input:
long long d = 4;

Output atteso:
long long expected = 6;
Input:
long d = 4;

Output atteso:
long expected = 6;

Spiegazione

1 ha un divisore e 3 ne ha due, ma 6 ne ha quattro (1, 2, 3, 6), quindi la risposta è 6.

Esempio 2
Input:
d = 9

Output atteso:
expected = 36
Input:
long long d = 9;

Output atteso:
long long expected = 36;
Input:
long d = 9;

Output atteso:
long expected = 36;

Spiegazione

28 ha sei divisori, mentre 36 = 2² × 3² ne ha 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), quindi la risposta è 36.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

T(k) = k(k + 1) / 2, e k e k + 1 non hanno fattori in comune.

Suggerimento 2

Dimezza quello pari tra k e k + 1, poi conta i divisori di ciascuna parte.

Suggerimento 3

Il numero di divisori di un prodotto di numeri coprimi è il prodotto dei rispettivi numeri di divisori.

Complessità attesa

tempo O(K √K) per K numeri triangolari provati, spazio aggiuntivo O(1)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.