NYOJ - 69 - 數的長度(斯特林公式)

描述

    N！階乘是一個非常大的數，大家都知道計算公式是N!=N*(N-1）······*2*1.現在你的任務是計算出N！的位數有多少（十進制）？

輸入

首行輸入n，表示有多少組測試資料(n<10)

随後n行每行輸入一組測試資料 N( 0 < N < 1000000 )

輸出

對于每個數N，輸出N!的（十進制）位數。

樣例輸入

3
1
3
32000      

樣例輸出

1
1
130271      

思路：題目要求n！的結果的位數。如果直接算出n！是不可取的。

n! = 1*2*3*4*5*...*(n-2)*(n-1)*n

n!的位數：log(10)n! = log(10)(1*2*3*4*5*...*(n-2)*(n-1)*n) = log(10)1+log(10)2+log(10)3+...log(10)n;

或者可以用公式：

斯特林公式  n！=sqrt（2*pi*n)*(n/e)^n , 那麼 n的階乘位數 = log10 (sqrt(2*pi*n)*(n/e)^n) +1 =0.5* log10 (2*pi*n)+n*log10(n/e) +1 ;

#include<iostream>
#include<cmath>
using namespace std;
int n,m;
double ans;
int main(){
	cin>>n;
	while(n--){
		ans = 1;
		cin>>m;
		while(m){
			ans += log10(m);
			m--;
		}
		cout<<(int)ans<<endl;
	}
	
	return 0;
}