HDOJ---1018 求N!的位数【斯特林公式

大数

时间限制：2000/1000 MS（Java/其他）内存限制：65536/32768 K（Java/其他）

提交总数：15969 已接受的提交：7061

问题描述

在许多应用程序中etc公式等于什么，需要非常大的整数。 其中一些应用程序使用密钥进行数据的安全传输、加密等。在这个问题中，你得到一个数字etc公式等于什么，你必须确定该数字的阶乘中的位数。

输入

输入由几行整数组成。 第一行包含一个整数n，这是要测试的案例数，后面是n行，每行一个整数1≤n≤10 7 。

输出

输出包含输入中出现的整数的阶乘的位数。

样本输入

2 10 20

示例输出

7 19

来源

亚洲 2002，达卡（孟加拉）

推荐

JG闪亮

注意：log()函数默认是loge()，在log(n)中，n必须是float或者double类型。

代码：

 1 /*斯特林[striling]公式(求阶乘(n!)的位数) 
 2 -10-05 13:49
 3 例如1000阶乘位数： 
 4 log10(1)+log10(2)+···+log10(1000)取整后加1 
 5 */
 6 
 7 #include 
 8  #include 
 9  int main()
10  {
11      int n,cas,i;
12      double sum;
13      scanf("%d",&cas);
14      while (cas--)
15      {
16          scanf("%d",&n);
17          sum=1;
18          for(i=1;i<=n;i++)   
19              sum+=log10((double)i);

20          printf("%d\n",(int)sum);
21      }
22      return 0;
23  }
24 /*
25 或
26 
27 #include 
28 #include 
29 #define PI 3.14159265 
30 int main(){ 
31 int len,N; 
32 while(scanf("%d",&N)!=EOF)
33 {
34 if(N==1)
35 len=1;
36 else
37 len=(int)ceil((N*log(N)-N+log(2*N*PI)/2)/log(10));ceil求上界，即不小于某值的最小整数 
38 //string公式lnN!=NlnN-N +0.5*ln( 2*N*pi) 

39 //而N次方阶乘的位数等于： 
40 //     log10(N!)取整后加1 
41 //    log10(N!)=lnN!/ln(10) 
42 
43 //ceil为求上界，即不小n的最小整数
44 //log取自然对数
45 printf("%d\n",len); 
46 }
47 return 0;
48 }*/

斯特林公式---处理阶乘和阶乘数字

1：放n！ 写成10^m次方的形式，如果m=2，表示三位数。

【维基百科】

[摘自别处] n! 可以表示为10的次方，即n!=10^M（10的M次方，10^2为3位数 M+1表示位数）且不小于M的最小整数为

n!的位数，公式两边取对数，M=log10^n! 那是：

M = log10^1+log10^2+log10^3...+log10^n

M的值可以通过循环求和来计算

, M 是 n!

 1 #include 
 2  #include 
 3  int main()
 4  {
 5      int n,cas,i;
 6      double sum;
 7      scanf("%d",&cas);
 8      while (cas--)
 9      {
10          scanf("%d",&n);
11          sum=1;
12          for(i=1;i<=n;i++)    sum+=log10((double)i);
13          printf("%d\n",(int)sum);
14      }
15      return 0;
16  }

2：斯特林公式的应用【没用，代码是别人的】

从斯特林[stringing]公式：lnN!=NlnN－N+0.5ln(2N*pi)

而N的阶乘的位数等于：log10(N!)四舍五入后加1

log10(N!)=lnN!/ln(10) 所以 len=lnN!/ln(10)+1

 1 #include
 2  #include
 3  const double PI=3.14159265;
 4  using namespace std;
 5  int main()
 6  {
 7      int t,n;
 8      double sum;
 9      cin>>t;
10      while(t--)
11      {   
12          cin>>n;
13          sum=(n*log(n) - n + 0.5*log(2*n*PI))/log(10)+1;
14          printf("%d/n",(int)sum);   
15      }
16      return 0;
17  }