爱华网hdu 1018 Big Number
这题我一开始白痴的暴力了一下，结果MLE了。~~然后果断上网找大牛写法，找到一个小公式，不错。介绍下
主要介绍一种算法Stirling：
log10(n!)=log10(1*2*3…*n)=log10(1)+log10(2)+…+log10(n)
《计算机程序设计艺术》中给出了另一个公式
n! = sqrt(2*π*n) * ((n/e)^n) * (1 +1/(12*n) +1/(288*n*n) + O(1/n^3))
π = acos(-1)
e = exp(1)
两边对10取对数
忽略log10(1 + 1/(12*n) +1/(288*n*n) + O(1/n^3)) ≈log10(1) = 0
得到公式
log10(n!) = log10(sqrt(2 * pi * n)) + n* log10(n/ e)。
得到就是位数啦。
#include<stdio.h>
#include<math.h>
#define pi 3.141592653
#define e 2.718281828
int main()
{
double n;
int T;
scanf("%d", &T);
while(T--)
{
scanf("%lf",&n);
int bit;
n = log10( sqrt( 2.0 * pi * n)) + n * log10( n / e);
bit = n;
if( n >bit)
bit++;
printf("%dn",bit);
}
return 0;
}
