Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Distinct Powers

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

2 ≤ lo ≤ hi ≤ 100

Ví dụ

Ví dụ 1
Đầu vào:
lo = 2
hi = 4

Kết quả mong đợi:
expected = 8
Đầu vào:
long long lo = 2;
long long hi = 4;

Kết quả mong đợi:
long long expected = 8;
Đầu vào:
long lo = 2;
long hi = 4;

Kết quả mong đợi:
long expected = 8;

Giải thích

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

Ví dụ 2
Đầu vào:
lo = 7
hi = 7

Kết quả mong đợi:
expected = 1
Đầu vào:
long long lo = 7;
long long hi = 7;

Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long lo = 7;
long hi = 7;

Kết quả mong đợi:
long expected = 1;

Giải thích

Only 7^7, so 1.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

Put the pairs in a set and count them.

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.