Tous les défis
Facile 0 résolus 0 % de réussite

Puissances distinctes

Compter les valeurs différentes de a puissance b pour a et b dans un intervalle.

Ce que vous allez apprendre

  • Ramener une base à sa plus petite racine
  • Comparer des puissances énormes sans les calculer
  • Compter des valeurs uniques avec un ensemble

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.