ACM-數論之Big Number——hdu1018

***************************************轉載請注明出處http://blog.csdn.net/lttree******************************************

Big Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 24823    Accepted Submission(s): 11267

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 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
        

Source Asia 2002, Dhaka (Bengal)  

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1018

題目内容：求n！的位數。

比如10！=3628800 是7位數。

我一直以為找規律，找啊找。。。

最後發現是一個 斯特林公式。。。

對數學的崇拜又加深了~\(≧▽≦)/~

斯特林公式（Stirling's approximation）是一條用來取n的階乘的近似值的數學公式。 一般來說，當n很大的時候，n階乘的計算量十分大，是以斯特林公式十分好用， 而且，即使在n很小的時候，斯特林公式的取值已經十分準确。

更精确為

或者

————以上均取自 百度百科

<span style="font-size:18px;">************************************** 
***************************************** 
*        Author:Tree                    * 
*From :http://blog.csdn.net/lttree      * 
* Title : Big Number                    * 
*Source: hdu 1018                       * 
* Hint : 斯特林公式                     * 
***************************************** 
****************************************/  

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

#define Pi acos(-1.0)
#define e 2.71828182

int main()
{
	int t,n;
	double m;
	scanf("%d",&t);
	while( t-- )
	{
		scanf("%d",&n);
		// 斯特林公式
		m = (double)n*log10(n*1.0/e)+0.5*log10(2.0*n*Pi);
		printf("%d\n",int(m)+1);
	}
	return 0;
}</span>