Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Các lũy thừa phân biệt

Đếm số giá trị khác nhau của a mũ b với a và b nằm trong một đoạn.

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

  • Đưa cơ số về căn nhỏ nhất của nó
  • So sánh các lũy thừa khổng lồ mà không cần tính
  • Đếm giá trị phân biệt bằng tập hợp

Đề bài

Xem bản gốc (English)

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ụ

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

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.

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

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.

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.