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