Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
\(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:
là 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ùaThầ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 6
Output
2
Note
\(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