Goal
For each of the given numbers \(A\), find the smallest integer \(N\), such that \(A^N < N!\) , where \(N! = 1 \cdot 2 \cdot ... \cdot N\)The numbers given can have up to 2 digits after decimal point.
Input
Line 1: An integer \(K\) for the number of inputs.
Line 2: \(K\) space separated numbers (can have a fractional part, e.g. 1.5): \( A_1 , A_2 , ... , A_K\)
Line 2: \(K\) space separated numbers (can have a fractional part, e.g. 1.5): \( A_1 , A_2 , ... , A_K\)
Output
Line 1: \(K\) space separated integers: \( N_1 , N_2 , ... , N_K\) .
Constraints
\(1 ≤ K ≤ 100\)
\(1 < A_i < 10000\)
\(1 < A_i < 10000\)
Solution
I first thought it's a fun number theoretic problem again, similar to dividing the factorial, where Legendre's formula could be used. However, \(A\) is a decimal number and so the whole thing doesn't make sense anymore. The only thing we can do is the following:
\[A^N< N!\Leftrightarrow N<\log_A{N!} = \sum\limits_{i=1}^N\log_Ai = \frac{1}{\log A} \sum\limits_{i=1}^N\log i\]
It follows that we simply loop over the logarithms until the stated condition breaks. The last integer \(N\) we see this way is the smallest fulfilling the initial statement.
var K = +readline();
var inputs = readline().split(' ');
var R = [];
for (var k = 0; k < K; k++) {
var i = 0
var s = 0;
var logA = Math.log(inputs[k]);
do {
s+= Math.log(++i);
} while(s <= i * logA);
R.push(i);
}
print(R.join(" "));