这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1018
好久没在HDOJ上做题了,一看这是Stirling公式,就做了~~~
第一种是暴力的解法,注意,不是本质的暴力,只是相对的暴力: f(n)=log10(1234......*n)+1=log10(1)+log10(2)+log10(3)+......log10(n)+1。 结果是406MS AC
#include
#include
using namespace std;
int main(){
int n,num,i;
double result;
for(scanf("%d",&n;);n;--n){
scanf("%d",#);
result=1;
for(i=1;i<=num;++i)
result+=log10(double(i));
printf("%d\n",int(result));
}
return 0;
}
第二种: Stirling定理:http://baike.baidu.com/view/2019233.htm?fr=ala0_1
n! = sqrt(2πn) * ((n/e)^n) 得到公式 log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e) + 1
#include
#include
const double PI=acos(-1.0),e=exp(1.0);
int main()
{
int t,n;
scanf("%d",&t;);
while(t--)
{
scanf("%d",&n;);
printf("%d\n",(int)(log10(sqrt(2*PI*n))+n*log10(n/e))+1);
}
return 0;
}