（ 數論專題 ）【斯特靈公式】

（ 數論專題 ）【斯特靈公式】

斯特林公式是一條用來取n的階乘的近似值的數學公式

一般來說，階乘的計算複雜度為線性。當要為某些極大大的n求階乘時，常見的方法複雜度不可接受。斯特林公式能夠将求解階乘的複雜度降低到對數級。而且，即使在n很小的時候，斯特林公式的取值已經十分準确。

斯特林公式可以用來估算某數階乘的大小，結合lg可以估算某數的階乘的位數，或者可以估算某數的階乘是另一個數的倍數。

給你一個整數n，求n！的位數。利用斯特靈公式求解n!的位數：

易知整數n的位數為[lgn]+1（ 證明：用科學計數法表示數n為1.xx * 10^k , 對這個數取對數就是k+log10(1.xx), 大約就是k+1位 ）。.利用Stirling公式計算n!結果的位數時，可以兩邊取對數，得:

log10(n!) = log10(2*n*Pi)/2+n*log10(n/e)

則答案為：   ans = log10(2*n*Pi)/2+n*log10(n/e) + 1

#include<bits/stdc++.h>

using namespace std;

const double pi = acos(-1);
const double e = exp(1);

signed main()
{
    int n;cin>>n;
    int w=1;
    for ( int i=1; i<=n; i++ ) w*=i;
    cout << w << endl;
//    cout << sqrt(2*acos(-1)*n)*pow(1.0*n/exp(1),n); // 輸出n!的Stirling值
    cout << int( log10(2*pi*n)/2+n*log10(1.0*n/e) ) + 1 << endl; // 輸出n!的位數

    return 0;
}