Mã bài:
getmcake
Điểm:
2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Tèo tuy bề ngoài có vẻ thanh niên nhưng thực chất đó là do cậu học code quá nhiều, còn tâm hồn của Tèo thì vẫn còn là thiếu nhi. Trung thu năm nay, phường của Tèo tổ chức một trò chơi dành cho các bé thiếu nhi. Người tham gia được cho trước số nguyên ~n, m~ và ~p~ (~p~ là số nguyên tố). Nhiệm vụ của người chơi là tìm số nguyên ~a~ sao cho ~(n!)^m~ chia hết cho ~p^a~. Người chơi sẽ nhận được số bánh trung thu bằng với số ~a~ mà họ tìm được. Vì là người mê bánh trung thu, Tèo nhất định sẽ tham gia và mong muốn giành về số bánh lớn nhất có thể. Bạn hãy giúp Tèo tính trước số bánh có thể đạt được.
Dữ liệu vào
- Một dòng chứa ~3~ số nguyên ~n, m, p~.
Kết quả
- Một số duy nhất là kết quả bài toán.
Giới hạn
- ~p \le 10^{18}~
- Subtask ~1~ ~(25\%)~: ~n \le 15,~ ~ m = 1~.
- Subtask ~2~ ~(25\%)~: ~n \le 15,~ ~ m \le 1000~
- Subtask ~3~ ~(50\%)~: ~n \le 10^{12},~ ~ m \le 1000~.
Ví dụ
Dữ liệu
6 3 3
Kết quả
6
Giải thích
- ~(6!)^3 = 373248000~ chia hết cho ~3^6 = 729~. Đây cũng là ~a~ cao nhất mà Tèo có thể tìm được.
Bình luận