[SPOJ] FACVSPOW – Factorial vs Power | 书脊

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

Consider two integer sequences f(n) = n! and g(n) = an, where n is a positive integer. For any integer a > 1 the second sequence is greater than the first for a finite number of values. But starting from some integer k, f(n) is greater thang(n) for all n >= k. You are to find the least positive value of n for which f(n) > g(n), for a given positive integer a > 1.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consist of a single number a.

Constraints

1 <= t <= 100000
2 <= a <= 106

Output

For each test print the least positive value of n for which f(n) > g(n).

Example

Input:
3
2
3
4

Output:
4
7
9

 Submit solution!

[SPOJ] FACVSPOW – Factorial vs Power | 书脊
题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n
分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code

https://github.com/ashish1294/BugFreeCodes/blob/master/Spoj/Factorial%20vs%20Power.c
int main()
{
    long long int i,a,j;
    dpsum[1]=0;
    for(i=2;i<3000000;i++)
        dpsum[i]=dpsum[i-1]+logl(i);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&a);
        {
            j=pow(e,(logl(a)+1));
            //printf("Approx =%lld\n",j);
            double ss = dpsum[j]/log(a);
            while(ss>j)
            {
                j--;
                ss = dpsum[j]/log(a);
            }
        }
        printf("%lld\n",j+1);
    }
    return 0;
}
Read full article from [SPOJ] FACVSPOW – Factorial vs Power | 书脊