Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Número triangular con muchos divisores

Encuentra el primer número triangular que tiene al menos d divisores.

Lo que aprenderás

  • Contar divisores a partir de la descomposición en factores primos
  • Usar la fórmula de los números triangulares
  • Separar un producto de factores coprimos

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.