2014年5月4日 星期日

UVa 1185 - Big Number

Problem link

Keyword: math, logarithm, DP

Algorithm:
We know that log(a*b) = log a + log b, so log n! = log 1 + log 2 + ... + log n.
Further more, we can get how many digits a number has by taking logarithm operation with a base of 10.
Also, there's a recursive function that N! = (N-1)! * N.

Code:
#include<cstdio>
#include<cmath>
double ans[ 10000001 ] = { 0, 1 };
int in, t;

int main()
{
    scanf( "%d", &t );

    for( int i = 2; i <= 10000000; ++i )
        ans[ i ] = ans[ i-1 ] + log10( i );
    while( t-- )
        scanf( "%d", &in ), printf( "%d\n", int( ans[ in ] ) );

    return 0;
} 

沒有留言:

張貼留言