Lũy thừa lớn nhất (Bản khó)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
BichSonNhat
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

BichSonNhat 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ù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, BichSonNhat đà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 ^ {12})\)

Output

  • In ra số nguyên dương \(k\) lớn nhất thõa mãn đề bài.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n ≤ 10^6\).

  • Subtask \(2\) (\(60\%\) 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