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