आसान 0 हल किए गए 0% स्वीकृति

Distinct Powers

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

2 ≤ lo ≤ hi ≤ 100

उदाहरण

उदाहरण 1
इनपुट:
lo = 2
hi = 4

अपेक्षित आउटपुट:
expected = 8
इनपुट:
long long lo = 2;
long long hi = 4;

अपेक्षित आउटपुट:
long long expected = 8;
इनपुट:
long lo = 2;
long hi = 4;

अपेक्षित आउटपुट:
long expected = 8;

व्याख्या

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

उदाहरण 2
इनपुट:
lo = 7
hi = 7

अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long lo = 7;
long long hi = 7;

अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long lo = 7;
long hi = 7;

अपेक्षित आउटपुट:
long expected = 1;

व्याख्या

Only 7^7, so 1.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

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

संकेत 3

Put the pairs in a set and count them.

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।