Đề bài
Lấy mọi a và mọi b từ lo đến hi rồi tính a^b. Một số giá trị bị trùng, ví dụ 2^4 = 4^2 = 16. Hãy đếm xem có bao nhiêu giá trị khác nhau. Các giá trị này rất lớn, nhưng bạn không bao giờ cần tính chúng: hãy viết a thành r^k, trong đó r không phải là lũy thừa đúng của số nào khác, khi đó a^b = r^(k × b). Hai lũy thừa bằng nhau khi và chỉ khi chúng có cùng r và cùng số mũ k × b.
Hãy viết distinct_powers(lo, hi).
Đầu vào
lo: Cơ số và số mũ nhỏ nhất.
hi: Cơ số và số mũ lớn nhất.
Đầu ra
Trả về số giá trị phân biệt của a^b với lo ≤ a ≤ hi và lo ≤ b ≤ hi.
Ràng buộc
2 ≤ lo ≤ hi ≤ 100
Ví dụ
Đầ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
Chín lũy thừa là 4, 8, 16, 9, 27, 81, 16, 64, 256. Số 16 xuất hiện hai lần, nên có 8 giá trị phân biệt.
Đầ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
Chỉ có 7^7, nên đáp án là 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tìm r nhỏ nhất và k lớn nhất sao cho r^k = a.
Gợi ý 2
a^b bằng r^(k × b), nên cặp (r, k × b) xác định duy nhất giá trị đó.
Gợi ý 3
Đưa các cặp vào một tập hợp rồi đếm.
Độ phức tạp mong đợi
thời gian O((hi − lo)² log hi), bộ nhớ phụ O((hi − lo)²)
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.