Problema
Os números triangulares contam os pontos de um triângulo com linhas de 1, 2, 3, ... pontos: T(1) = 1, T(2) = 3, T(3) = 6 e T(k) = k(k + 1) / 2. Percorra-os em ordem e pare no primeiro que tiver pelo menos d divisores positivos (o 1 e o próprio número contam).
Implemente highly_divisible_triangular(d).
Contar os divisores um a um é lento demais para os casos maiores. Em vez disso, fatore o número: se n = p^a × q^b × ..., ele tem (a + 1)(b + 1)... divisores. Como k e k + 1 não têm fator em comum, você pode fatorá-los separadamente.
Entrada
d: a quantidade de divisores exigida.
Saída
Retorne o primeiro número triangular com pelo menos d divisores.
Restrições
1 ≤ d ≤ 300
Exemplos
Entrada:
d = 4
Saída esperada:
expected = 6
Entrada:
long long d = 4;
Saída esperada:
long long expected = 6;
Entrada:
long d = 4;
Saída esperada:
long expected = 6;
Explicação
1 tem um divisor e 3 tem dois, mas 6 tem quatro (1, 2, 3, 6), então a resposta é 6.
Entrada:
d = 9
Saída esperada:
expected = 36
Entrada:
long long d = 9;
Saída esperada:
long long expected = 36;
Entrada:
long d = 9;
Saída esperada:
long expected = 36;
Explicação
28 tem seis divisores e 36 = 2² × 3² tem 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), então a resposta é 36.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
T(k) = k(k + 1) / 2, e k e k + 1 não têm fator em comum.
Dica 2
Divida por 2 aquele entre k e k + 1 que for par e depois conte os divisores de cada parte.
Dica 3
A quantidade de divisores de um produto de números primos entre si é o produto das quantidades de cada um.
Complexidade esperada
tempo O(K √K) para K números triangulares testados, espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.