Einfach 0 gelöst 0% Erfolgsquote

Distinct Powers

Count the different values of a to the power b for a and b in a range.

Das lernst du

  • Reduce a base to its smallest root
  • Compare huge powers without computing them
  • Count unique values with a set

Problem

Übersetzung anzeigen

Take every a and every b from lo to hi and compute a^b. Some values repeat, like 2^4 = 4^2 = 16. Count how many different values there are. The values are huge, but you never need them: write a as r^k where r is not itself a perfect power, and a^b = r^(k × b). Two powers are equal exactly when they share the same r and the same exponent k × b.

Implement distinct_powers(lo, hi).

Input

lo: The smallest base and exponent.

hi: The largest base and exponent.

Output

Return the number of distinct values of a^b with lo ≤ a ≤ hi and lo ≤ b ≤ hi.

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

The nine powers are 4, 8, 16, 9, 27, 81, 16, 64, 256. 16 appears twice, so there are 8 distinct values.

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

Only 7^7, so 1.

So gehst du vor

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

Hinweis 1

Find the smallest r and largest k with r^k = a.

Hinweis 2

a^b equals r^(k × b), so the pair (r, k × b) identifies the value.

Hinweis 3

Put the pairs in a set and count them.

Erwartete Komplexität

O((hi − lo)² log hi) time, O((hi − lo)²) extra space

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.