Problema
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
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.
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.