Lũy thừa lớn nhất (Bản dễ)
Xem PDFlà một thanh niên rất thích những bài toán liên quan đến con số. Thấy thế, trong mùa \(Translate\) \(COVID\) vô cùng chán nản này, thầy Hùng quyết định đánh đố học trò của mình:
Thầy sẽ cho bạn 2 số nguyên dương \(n\) và \(m\) bất kỳ, nhiệm vụ của bạn là tìm số nguyên dương \(k\) lớn nhất sao cho \(n!\) \(=\) \(1 \times 2 \times 3 \times 4 \times .. \times n\) chia hết cho \(m^k\).
Nếu không tìm được số \(k\) thõa mãn, in ra \(-1\).
Cảm thấy độ quá dễ của bài toán, đành nhường câu đố này cho các bạn!
Input
- Dòng đâu tiên chứa số \(2\) nguyên dương \(n, m\) \((2 ≤ n, m ≤ 10 ^ 6)\)
Output
- In ra số nguyên dương \(k\) lớn nhất thõa mãn đề bài.
Scoring
-
Subtask \(1\) (\(30\%\) số điểm): \(n ≤ 10\).
-
Subtask \(2\) (\(30\%\) số điểm): \(n ≤ 10^3\).
-
Subtask \(3\) (\(40\%\) số điểm): không ràng buộc gì thêm.
Example
Test 1
Input
6 6Output
2Note
\(n = 6! = 720\), $ m = 6 $, số \(k\) lớn nhất là \(2\) nên \(m = 6 ^ 2 = 36\) và \(720\) \(\vdots\) \(36\).
Bình luận
dùng python chạy test cuối bị TLE :(( (không if test)
solution for problem :))))
Bài này có thể tăng giới hạn \(N, M\) lên \(10^{12}\) đấy