Problema
Los números triangulares cuentan los puntos de un triángulo con filas de 1, 2, 3, ... puntos: T(1) = 1, T(2) = 3, T(3) = 6 y, en general, T(k) = k(k + 1) / 2. Recórrelos en orden y detente en el primero que tenga al menos d divisores positivos (el 1 y el propio número también cuentan).
Implementa highly_divisible_triangular(d).
Contar los divisores uno por uno es demasiado lento para los casos grandes. En su lugar, descompón el número en factores primos: si n = p^a × q^b × ..., tiene (a + 1)(b + 1)... divisores. Como k y k + 1 no tienen factores comunes, puedes factorizarlos por separado.
Entrada
d: la cantidad de divisores necesaria.
Salida
Devuelve el primer número triangular con al menos d divisores.
Restricciones
1 ≤ d ≤ 300
Ejemplos
Entrada:
d = 4
Salida esperada:
expected = 6
Entrada:
long long d = 4;
Salida esperada:
long long expected = 6;
Entrada:
long d = 4;
Salida esperada:
long expected = 6;
Explicación
1 tiene un divisor y 3 tiene dos, pero 6 tiene cuatro (1, 2, 3, 6), así que la respuesta es 6.
Entrada:
d = 9
Salida esperada:
expected = 36
Entrada:
long long d = 9;
Salida esperada:
long long expected = 36;
Entrada:
long d = 9;
Salida esperada:
long expected = 36;
Explicación
28 tiene seis divisores y 36 = 2² × 3² tiene 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), así que la respuesta es 36.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
T(k) = k(k + 1) / 2, y k y k + 1 no tienen ningún factor común.
Pista 2
Divide entre 2 el que sea par de k y k + 1, y luego cuenta los divisores de cada parte.
Pista 3
La cantidad de divisores de un producto de números coprimos es el producto de sus cantidades.
Complejidad esperada
tiempo O(K √K) para K números triangulares probados, espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.