Problem: http://www.spoj.com/problems/FACVSPOW/

Shortly, you are given a number A as input and you want to find such an N for which

N! > A^N

You must be able to calculate N! fast enough since O(N) would be too slow.

We can use Stirling’s approximation for which:

N! ~ sqrt(2*PI*N) * (N/e)^N

=> we are searching for such an N for which

sqrt(2*PI*N) * (N/e)^N > A^N

or

N * (2*PI*N)^(1/2N) >= A*e

We can do binary search on N and calculate the answer in log(N).

#include <cstdio> #include <cmath> #include <iostream> using namespace std; int calc(int a) { int l = 0, r = 10000000000; int n=0; static double E = exp(1.0); static double PI = 3.14159265358979323846; double want = E * (double)a; while (l <= r) { int m = (l+r)/2; double val = pow(PI*2.0* ((double)m), 1.0 / (2.0 * (double)m))*(double)m; if (val <= want) { l = m+1; } else { r = m-1; n = m; } } return n; } int main() { int t; scanf("%d", &t); while (t--) { int a; scanf("%d", &a); printf("%dn",calc(a)); } return 0; }