hdu 1018 Big Number(数学)

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 7 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
题目大意就是给出你一个n让你计算出n!有多少位。一开始以为大数计算而已,但是再一看数据n的范围太大了,如果要是真正计算出来的话必然TLE。
我们知道这样一个公式:对于一个数x,他的位数为cnt=(int)log10(x)+1.
证明如下:
对于一个正整数x,可以得到这样一个不等式:10^(cnt-1)<=x<10^cnt的形式。那么x必然是cnt位。那么两边同时取log10的话,cnt-1<=log10(x)<cnt.那么(int)log10(x)+1=cnt.得证。
我们可以把1-n的所有的阶乘看成X,那么X可以看成1*2*3*..*n,然后我们就可以得出ans=(int)(log10(1)+log10(2)+…log10(n))+1这样就可以解决问题了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注