Big Number

Big Number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26744 Accepted Submission(s): 12173

Problem Description

In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.

Input

Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 10⁷ on each line.

Output

The output contains the number of digits in the factorial of the integers appearing in the input.

Sample Input

2 10 20

Sample Output

7 19

刚看到题目，第一反应便想到大数，但是看看题目，给出的数据可能 达到 10^7 的级别，这么大的数，求阶乘！  oh，my god！ 要知道，10000000 的阶乘有六千万多位。

还好，我们有公式， log10(n!)=(0.5*log(2*PI*n)+n*log(n)-n)/log(10) ， 这里利用了 log10 (N)=ln(N)/ln(10);

公式的名字是 斯特林公式 维基百科的链接 http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E6%9E%97%E5%85%AC%E5%BC%8F

#include <stdio.h>
#include <math.h>
#include<string.h>
#include <stdlib.h>

#define PI 3.14159265
int main()
{
  int n,t,digit;
  scanf("%d",&n);
  while(n--)
  {
    scanf("%d",&t);
    digit=(int)((0.5*log(2*PI*t)+t*log(t)-t)/log(10));
    printf("%d\n",digit+1);                        
  }
  system("pause");
  return 0;    
}