51nod1130N的阶乘的长度V2（斯特林近似）

51nod 1130 N的阶乘的长度 V2（斯特林近似）

使用 S t i r l i n g Stirling Stirling 公式

n ! = 2 π n ( n e ) n n!=sqrt{2pi n}(dfrac{n}{e})^n n!=2πn ​(en​)n

⇒ l e n ( n ! ) = log ⁡ 10 ( n ! ) + 1 Rightarrow len(n!)=log_{10}(n!)+1 ⇒len(n!)=log10​(n!)+1

= 1 2 log ⁡ 10 ( 2 π n ) + n log ⁡ 10 ( n e ) + 1 =dfrac{1}{2}log_{10}(2pi n)+nlog_{10}(dfrac{n}{e})+1 =21​log10​(2πn)+nlog10​(en​)+1

时间复杂度： O ( 1 ) O(1) O(1)

#includeusing namespace std;typedef long long ll;typedef unsigned long long ull; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;const int hashmod[4] = {402653189,805306457,1610612741,998244353};#define mst(a,b) memset(a,b,sizeof a)#define db double#define PII pair#define PLL pair#define x first#define y second#define pb emplace_back#define SZ(a) (int)a.size()#define rep(i,a,b) for(int i=a;i<=b;++i)#define per(i,a,b) for(int i=a;i>=b;--i)#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){for(int i=1;i//x=max(x,y) x=min(x,y)void cmx(T &x,T y){if(xvoid cmn(T &x,T y){if(x>y) x=y;}int n;const db pi = acos(-1.0);int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);//printf("%fn",exp(1));double s = 0.5*log10(2*pi*n)+n*log10(n/exp(1)) +1;printf("%lldn",(ll)s);}return 0;}