Todos os desafios
Médio 0 resolvidos 0% de aceitação

Número triangular com muitos divisores

Encontre o primeiro número triangular que tem pelo menos d divisores.

O que você vai aprender

  • Contar divisores a partir da fatoração em primos
  • Usar a fórmula dos números triangulares
  • Separar um produto de fatores primos entre si

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.