Editorial for ICPC NAQ 2016 G - Inverse Factorial - Olympiads Online Judge

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 \ge 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$ ~\lfloor \log_{10}(x) \rfloor + 1~.
Let $\displaystyle L_k := \log_{10}(k!) = \log_{10} \left(\prod_{i=1}^k i\right) = \sum_{i=1}^k \log_{10}(i)$
Then the length of $k!$ ~k!~ is $\lfloor L_k \rfloor + 1$ ~\lfloor L_k \rfloor + 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)$ ~\mathcal 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.