Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Verschiedene Potenzen

Zähle die verschiedenen Werte von a hoch b für a und b aus einem Bereich.

Das lernst du

  • Eine Basis auf ihre kleinste Wurzel zurückführen
  • Riesige Potenzen vergleichen, ohne sie zu berechnen
  • Verschiedene Werte mit einer Menge zählen

Problem

Nimm jedes a und jedes b von lo bis hi und berechne a^b. Manche Werte kommen mehrfach vor, zum Beispiel 2^4 = 4^2 = 16. Zähle, wie viele verschiedene Werte es gibt. Die Werte sind riesig, aber du brauchst sie gar nicht: Schreibe a als r^k, wobei r selbst keine echte Potenz ist, dann gilt a^b = r^(k × b). Zwei Potenzen sind genau dann gleich, wenn sie dasselbe r und denselben Exponenten k × b haben.

Implementiere distinct_powers(lo, hi).

Eingabe

lo: Die kleinste Basis und der kleinste Exponent.

hi: Die größte Basis und der größte Exponent.

Ausgabe

Gib die Anzahl der verschiedenen Werte von a^b mit lo ≤ a ≤ hi und lo ≤ b ≤ hi zurück.

Einschränkungen

2 ≤ lo ≤ hi ≤ 100

Beispiele

Beispiel 1
Eingabe:
lo = 2
hi = 4

Erwartete Ausgabe:
expected = 8
Eingabe:
long long lo = 2;
long long hi = 4;

Erwartete Ausgabe:
long long expected = 8;
Eingabe:
long lo = 2;
long hi = 4;

Erwartete Ausgabe:
long expected = 8;

Erläuterung

Die neun Potenzen sind 4, 8, 16, 9, 27, 81, 16, 64, 256. Die 16 kommt zweimal vor, es gibt also 8 verschiedene Werte.

Beispiel 2
Eingabe:
lo = 7
hi = 7

Erwartete Ausgabe:
expected = 1
Eingabe:
long long lo = 7;
long long hi = 7;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long lo = 7;
long hi = 7;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

Es gibt nur 7^7, also 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Finde das kleinste r und das größte k mit r^k = a.

Hinweis 2

a^b ist gleich r^(k × b), also bestimmt das Paar (r, k × b) den Wert eindeutig.

Hinweis 3

Lege die Paare in einer Menge ab und zähle sie.

Erwartete Komplexität

Zeit O((hi − lo)² log hi), zusätzlicher Speicher O((hi − lo)²)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.