HDOJ 1018 Big Number

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1018

好久没在HDOJ上做题了,一看这是Stirling公式,就做了~~~

第一种是暴力的解法,注意,不是本质的暴力,只是相对的暴力:
f(n)=log10(1*2*3*4*……*n)+1=log10(1)+log10(2)+log10(3)+……log10(n)+1。
结果是406MS AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
 
int main(){
    int n,num,i;
    double result;
    for(scanf("%d",&n);n;--n){
        scanf("%d",&num);
        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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio> 
#include<cmath> 
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; 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1018 Big Number》有2个想法

  1. 对于 log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e)+1
    是不是 log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e) 但是n!的位数才需要+1 ?

发表评论

电子邮件地址不会被公开。 必填项已用*标注