FACVSPOW - Factorial vs Power 数学方法 + 二分

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

求解n! > a^n最小的整数n

对于有n!和a^n的东西，一般是取ln

然后就是求解

(ln(1) + ln(2) + .... + ln(n)) / n > ln(a)的最小整数n

发现左边的函数单调，所以可以预处理出来，右边最大值是ln(1e6)

所以预处理5e6个。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 5e6 + ;

double f[maxn];

void init() {

    for (int i = ; i <= maxn - ; ++i) {

        f[i] = (f[i - ] * (i - ) + log(i * 1.0)) / (i * 1.0);

    }

//    for (int i = 1; i <= 100; ++i) {

//        cout << f[i] << endl;

//    }

}

int a;

double up;

const double eps = 1e-;

bool bigger(double a, double b) {

    return a - b > eps;

}

void work() {

    scanf("%d", &a);

    up = log(a * 1.0);

    int be = , en = maxn - ;

    while (be <= en) {

        int mid = (be + en) >> ;

        if (bigger(f[mid], up)) {

            en = mid - ;

        } else be = mid + ;

    }

    printf("%d\n", be);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    init();

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

据说

ln(n!) ≈ (n * ln(n)) - n + (1 / 2 * ln(2 * PI * n));