Problème
Prenez chaque a et chaque b de lo à hi et calculez a^b. Certaines valeurs reviennent plusieurs fois, comme 2^4 = 4^2 = 16. Comptez le nombre de valeurs différentes. Les valeurs sont énormes, mais vous n'avez jamais besoin de les calculer : écrivez a sous la forme r^k, où r n'est pas lui-même une puissance parfaite, et alors a^b = r^(k × b). Deux puissances sont égales exactement lorsqu'elles ont le même r et le même exposant k × b.
Implémentez distinct_powers(lo, hi).
Entrée
lo : la plus petite base et le plus petit exposant.
hi : la plus grande base et le plus grand exposant.
Sortie
Renvoyez le nombre de valeurs distinctes de a^b avec lo ≤ a ≤ hi et lo ≤ b ≤ hi.
Contraintes
2 ≤ lo ≤ hi ≤ 100
Exemples
Entrée :
lo = 2
hi = 4
Sortie attendue :
expected = 8
Entrée :
long long lo = 2;
long long hi = 4;
Sortie attendue :
long long expected = 8;
Entrée :
long lo = 2;
long hi = 4;
Sortie attendue :
long expected = 8;
Explication
Les neuf puissances sont 4, 8, 16, 9, 27, 81, 16, 64, 256. 16 apparaît deux fois, il y a donc 8 valeurs distinctes.
Entrée :
lo = 7
hi = 7
Sortie attendue :
expected = 1
Entrée :
long long lo = 7;
long long hi = 7;
Sortie attendue :
long long expected = 1;
Entrée :
long lo = 7;
long hi = 7;
Sortie attendue :
long expected = 1;
Explication
Il n'y a que 7^7, donc 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Trouvez le plus petit r et le plus grand k tels que r^k = a.
Indice 2
a^b est égal à r^(k × b), donc le couple (r, k × b) identifie la valeur.
Indice 3
Mettez les couples dans un ensemble et comptez-les.
Complexité attendue
temps O((hi − lo)² log hi), espace supplémentaire O((hi − lo)²)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.