When n! is written in base b, it may end in a run of zero digits. Given n and b, report how many trailing zeros n! has in base b. Equivalently, this is the largest integer k such that b**k divides n! (and 0 if no positive power of b divides n!).
A single line with two integers n and b.
A single integer: the number of trailing zeros of n! written in base b.
Example 1
Input
10 2
Expected
8
Explanation
The exponent of 2 in 10! is 5+2+1 = 8, so 10! ends in 8 zeros in base 2.
Example 2
Input
25 10
Expected
6
Explanation
Base 10 zeros are limited by the exponent of 5 in 25!, which is 5+1 = 6.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →