Editorial for ICPC NAQ 2016 G - Inverse Factorial

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

It is guaranteed that the number of digits of $n!$ $n!$ is at most $10^6$ $10^{6}$ . This implies that $n < 3 \cdot 10^5$ $n < 3 \cdot 10^{5}$ (found by experimentation).
A naive approach computing factorials will be too slow, due to the overhead of big integer arithmetic.
Instead we can notice that, when $n \ge 10$ $n \geq 10$ , each factorial can be uniquely identified by its length (i.e. number of digits).
The length of an integer $x$ $x$ can be computed as $\lfloor \log_{10}(x) \rfloor + 1$ $⌊ \log_{10} (x) ⌋ + 1$ .
Let $\displaystyle L_k := \log_{10}(k!) = \log_{10} \left(\prod_{i=1}^k i\right) = \sum_{i=1}^k \log_{10}(i)$ $L_{k} := \log_{10} (k!) = \log_{10} (\prod_{i = 1}^{k} i) = \sum_{i = 1}^{k} \log_{10} (i)$
Then the length of $k!$ $k!$ is $\lfloor L_k \rfloor + 1$ $⌊ L_{k} ⌋ + 1$ .
Using the fact that $L_{k+1} = L_k + \log_{10}(k+1)$ $L_{k + 1} = L_{k} + \log_{10} (k + 1)$ , we can successively compute $L_1, L_2, \dots$ $L_{1}, L_{2}, \dots$ , until we find the factorial with the required length.
Each step takes $\mathcal O(1)$ $O (1)$ time, and the answer will be found in at most $3 \cdot 10^5$ $3 \cdot 10^{5}$ steps.
Handle $n < 10$ $n < 10$ as special cases. As $0! = 1! = 1$ $0! = 1! = 1$ , make sure you output $1$ $1$ when the input is $1$ $1$ (the output should be positive).

Comments

There are no comments at the moment.