Under construction

Still being built. Things may change

Factorial

Interview

Time limit1sMemory limit512 MB

Summary
Given N and a prime A, find the largest k such that A^k divides N! (the exponent of A in the prime factorization of N!).
Level

Easy3 of 10

Topics
Number theory, Math, Implementation
Solved
No attempts yet

Problem

음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1)

Input

첫째 줄에 정수 N과 A가 사이에 공백을 두고 주어진다. (0 ≤ N < 231, 2 ≤ A ≤ 11, A는 소수)

Output

첫째 줄에 최대의 음이 아닌 정수 k를 출력한다.

Examples4

  1. Example 1

    Input
    5 2
    Expected output
    3

  2. Example 2

    Input
    10 2
    Expected output
    8

  3. Example 3

    Input
    10 3
    Expected output
    4

  4. Example 4

    Input
    100 5
    Expected output
    24