Bậc lũy thừa

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho một số nguyên dương \(n\) và một số nguyên tố \(p\). Hãy tìm ra bậc lũy thừa của \(p\) trong phân tích thừa số nguyên tố của \(n!\). Ví dụ \(n = 4, p = 2\) phân tích thừa số nguyên tố của \(4! = 24 = 2^3 \times 3\) vậy bậc lũy thừa của \(2\) trong phân tích thừa số nguyên tố \(4!\) là \(3\).

Input

Dòng đầu tiên chứa giá trị \(n, p (1 \leq n, p \leq 10^{9})\).

Output

In ra một số duy nhất là kết quả của bài toán.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

4 2

Output

3

Ví dụ 2

Input

24 2

Output

22

Giải thích ví dụ

• Ví dụ 1:

  • Input: 4 2
  • Output: 3
  • Giải thích: Phân tích thừa số nguyên tố của 4! là 2^3 × 3. Bậc lũy thừa của 2 trong phân tích này là 3.

• Ví dụ 2:

  • Input: 24 2
  • Output: 22
  • Giải thích: Phân tích thừa số nguyên tố của 24! có bậc lũy thừa của 2 là 22.

Bài tập này: E: Khó

Thông tin học tập

• Buổi: B08
• Concepts: advanced arithmetic and number theory
• Giới hạn kiến thức: B01-B08
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30