P3927 SAC E#1 - A Medium-Difficulty Problem: Factorial

SOL 君 (Hearthstone streamer) and SOL 菌 (Perfect Information Classroom instructor) are good friends.

SOL 君 likes factorials, while SOL 菌 enjoys studying number bases. One day, SOL 君 showed off to SOL 菌 by casually computing the factorial of $n$. SOL 菌 was unconvinced and immediately wanted to compute the number of trailing zeros of this number in base $k$. However, SOL 菌 is not skilled enough, so he asks you for help.

Each input contains a single line with two integers $n,k$.

Output a single integer: the number of trailing zeros of $n!$ in base $k$.

- For $20\%$ of the testdata, $n \le 1000000, k = 10$. - For another $20\%$ of the testdata, $n \le 20， k \le 36$. - For $100\%$ of the testdata, $n \le 10^{12}，k \le 10^{12}$. ### Update 1. Each test point contains only one test case. 2. $k$ will not be $1$. 3. Now the std does not overflow `long long`. 4. If there is any problem with the testdata, contact icy (it is recommended not to code to the data). Translated by ChatGPT 5