[SPOJ] FACVSPOW – Factorial vs Power

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

---

题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n

---

分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        double power = 0;
        double fact = 0;
        int cur = 2;
        double temp = Math.log(n);
        while (true) {
            fact += Math.log(cur); //
            power = temp * cur;
            if (fact > power) {
                out.printLine(cur);
                break;
            }
            cur++;
        }
}

可是tmd怎么也过不了. 后来想想是二分搜索, 首先, 假设n可以满足, 那么n+1肯定满足. 所以我们可以用二分搜索每次忽略一半. 其次就是怎么计算fact. 翻书啊,翻书 翻到了Stirlings Approximation, 真是简便的公式: .

然后就是low bound就是2*a吧, 但是high bound是啥啊…我数学不好, 真的算不出来. 就靠试数了..反正spoj也没提交限制…

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int a = in.readInt();
        int l = 2;
        int r = 3000000;
        int res = Integer.MAX_VALUE;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (compare(a,mid)){
                res = Math.min(res, mid);
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        out.printLine(res);
    }