Trailing Loves (or L'oeufs?)
Contest: Codeforces Round 538 (Div. 2)
Difficulty rating: 1700
Tags: brute force, implementation, math, number theory

Aki is fond of numbers, especially those with trailing zeros. For example, the number $$$9200$$$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers $$$n$$$ and $$$b$$$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $$$b$$$-ary (in the base/radix of $$$b$$$) representation of $$$n\,!$$$ (factorial of $$$n$$$).

Input format:
The only line of the input contains two integers $$$n$$$ and $$$b$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le b \le 10^{12}$$$).

Output format:
Print an only integer — the number of trailing zero digits in the $$$b$$$-ary representation of $$$n!$$$

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$6!_{(10)} = 720_{(10)} = 880_{(9)}$$$.

In the third and fourth example, $$$5!_{(10)} = 120_{(10)} = 1111000_{(2)}$$$.

The representation of the number $$$x$$$ in the $$$b$$$-ary base is $$$d_1, d_2, \ldots, d_k$$$ if $$$x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$$$, where $$$d_i$$$ are integers and $$$0 \le d_i \le b - 1$$$. For example, the number $$$720$$$ from the first example is represented as $$$880_{(9)}$$$ since $$$720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$$$.

You can read more about bases here.

Example input:
6 9

Example output:
1

Example input:
38 11

Example output:
3

Editorial:
The problem can be reduced to the following: finding the maximum $$$r$$$ that $$$n\,!$$$ is divisible by $$$b^r$$$.
By prime factorization, we will have the following: $$$b = {p_1}^{y_1} \cdot {p_2}^{y_2} \cdot \ldots \cdot {p_m}^{y_m}$$$.
In a similar manner, we will also have: $$$n\,! = {p_1}^{x_1} \cdot {p_2}^{x_2} \cdot \ldots \cdot {p_m}^{x_m} \cdot Q$$$ (with $$$Q$$$ being coprime to any $$$p_i$$$ presented above).
The process of finding $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$, $$$y_1$$$, $$$y_2$$$, ..., $$$y_m$$$ can be done by normal prime factorization of the value $$$b$$$.
The process of finding $$$x_1$$$, $$$x_2$$$, ..., $$$x_m$$$ is a little bit more tricky since the integer they were originated ($$$n\,!$$$) is too huge to be factorized manually. Still the factorial properties gave us another approach: for each $$$p_i$$$, we can do the following:
- Initially, denote $$$x_i = 0$$$.
- Repeatedly do the following: add $$$\lfloor \frac{n}{p_i} \rfloor$$$ to $$$x_i$$$, then divide $$$n$$$ by $$$p_i$$$. The loop ends when $$$n$$$ is zero.
After all, we can obtain the final value $$$r$$$ as of following: $$$r = \displaystyle \min_{i \in [1, m]} \lfloor \frac{x_i}{y_i} \rfloor$$$.
Total complexity: $$$\mathcal{O} \left( \sqrt{b} + \log(b) \cdot \log(n) \right)$$$ (as the number of prime factors of an integer $$$b$$$ will not surpass $$$\log(b)$$$).