Spoj FACVSPOW – Cpp solution

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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *