DEGREE - Số lượng bậc
Giới hạn- Thời gian: 0.065s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một số nguyên dương A gọi là có bậc K đối với cơ số B nếu như :
• A = B^x1 + B^x2 + … + B^xk
( trong đó x1 , x2 , … , xk là các số nguyên không âm thoả mãn x1 <> x2 <> x3 … <> xk )
Ví dụ :
• 17 có bậc 2 đối với cơ số 2 vì 17 = 2^4 + 2^0 .
• 151 có bậc 3 đối với cơ số 5 vì 151 = 5^3 + 5^2 + 5^0.
Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.
Giới hạn :
• 1 <= X <= Y <= 10^9
• 1 <= K <= 25, 2 <= B <= 9
• Chạy được với bộ nhớ thông báo < 800 K bạn mới thực sự là thành công
Input
1 dòng gồm 4 số nguyên dương X , Y , K , B
Output
Gồm 1 dòng duy nhất ghi ra số lượng số tìm được .
Example
Input: 15 20 2 2 Output: 3( Giải thích : Đó là các số 17 = 2^4 + 2^0 , 18 = 2^4 + 2^1 , 20 = 2^4 + 2^2 )
- Người up: hard7771988
- Nguồn bài: Rybinsk State Avia Academy