F. Factorial
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 231 Accepted Runs: 61
Robby is a clever boy, he can do multiplication very quickly, even in base-2 (binary system), base-16 (hexadecimal system) or base-100000.
Now he wants to challenge your computer, the task is quite simple: Given a positive integer N, if we express the N ! (N ! = N * (N - 1) * (N - 2) * ... * 2 * 1) in base-B, how many ZEROs there will be at the end of the number. Can you make a wonderful program to beat him?
Input
Each test case contain one line with two numbers N and B. (1 ≤ N ≤ 109, 2 ≤ B ≤ 100000)
The input is terminated with N = B = 0.
Output
Output one line for each test case, indicating the number of ZEROs.Sample Input
7 10
7 10000
7 2
0 0
Sample Output
1
0
4
Hint
7! = (5040)10, so there will be one zero at the end in base-10. But in base-10000, the number (5040)10 can be expressed in one non-zero digit, so the second answer is 0. In base-2, 7! = (1001110110000)2, so the third answer is 4.
Problem Setter: RoBa
Source: Tianjin Metropolitan Collegiate Programming Contest 2007
Problem ID in problemset: 2845
Submit Back Runs Statistics Clarifications
Tianjin University Online Judge v1.2.4