Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Potências distintas

Conte os valores diferentes de a elevado a b para a e b em um intervalo.

O que você vai aprender

  • Reduzir uma base à sua menor raiz
  • Comparar potências enormes sem calculá-las
  • Contar valores únicos com um conjunto

Problema

Ver original (inglês)

Tome todo a e todo b de lo a hi e calcule a^b. Alguns valores se repetem, como 2^4 = 4^2 = 16. Conte quantos valores diferentes existem. Os valores são enormes, mas você nunca precisa deles: escreva a como r^k, em que r não é ele mesmo uma potência perfeita, e então a^b = r^(k × b). Duas potências são iguais exatamente quando têm o mesmo r e o mesmo expoente k × b.

Implemente distinct_powers(lo, hi).

Entrada

lo: a menor base e o menor expoente.

hi: a maior base e o maior expoente.

Saída

Retorne a quantidade de valores distintos de a^b com lo ≤ a ≤ hi e lo ≤ b ≤ hi.

Restrições

2 ≤ lo ≤ hi ≤ 100

Exemplos

Exemplo 1
Entrada:
lo = 2
hi = 4

Saída esperada:
expected = 8
Entrada:
long long lo = 2;
long long hi = 4;

Saída esperada:
long long expected = 8;
Entrada:
long lo = 2;
long hi = 4;

Saída esperada:
long expected = 8;

Explicação

As nove potências são 4, 8, 16, 9, 27, 81, 16, 64, 256. O 16 aparece duas vezes, então há 8 valores distintos.

Exemplo 2
Entrada:
lo = 7
hi = 7

Saída esperada:
expected = 1
Entrada:
long long lo = 7;
long long hi = 7;

Saída esperada:
long long expected = 1;
Entrada:
long lo = 7;
long hi = 7;

Saída esperada:
long expected = 1;

Explicação

Só existe 7^7, então 1.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Encontre o menor r e o maior k com r^k = a.

Dica 2

a^b é igual a r^(k × b), então o par (r, k × b) identifica o valor.

Dica 3

Coloque os pares em um conjunto e conte-os.

Complexidade esperada

tempo O((hi − lo)² log hi), espaço extra O((hi − lo)²)

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.