首页 > > 程序设计 > C/C++ >

51nod 1130 N的阶乘的长度(斯特林近似)

2018-06-17 22:06:01来源：未知阅读 ()

输入N求N的阶乘的10进制表示的长度。例如6! = 720，长度为3。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000)
第2 - T + 1行：每行1个数N。（1 <= N <= 10^9)

Output

共T行，输出对应的阶乘的长度。

Input示例

Output示例

2
3
3

斯特林公式是一条用来取n阶乘近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大

所以斯特灵公式十分好用，而且，即使在n很小的时候，斯特灵公式的取值已经十分准确

公式为： $n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}.$

这就是说，对于足够大的整数n，这两个数互为近似值。更加精确地： $\lim_{n \rightarrow \infty} {\frac{n!}{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}} = 1$

或 $\lim_{n \rightarrow \infty} {\frac{e^n\, n!}{n^n \sqrt{n}}} = \sqrt{2 \pi}.$ 然后取一下log（）＋ 1就出来了

简单说

n!=n*(n-1)*(n-2)*......*3*2*1

∴lg(n!)=lg(n)+lg(n-1)+lg(n-2)+......+lg(3)+lg(2)+lg(1);

Stirling数求N!的位数:log10(n!)=0.5 * log10(2 * PI * n) + n * log10(n / e);

 1 #include <stdio.h>
 2 #include <math.h>
 3 #define e 2.718281828459
 4 #define pi 3.1415926
 5 int main(){
 6     int n, t;
 7     long long sum;
 8     scanf("%d",&t);
 9     while(t--){
10         scanf("%d",&n);
11         sum=1+0.5*log10(2*pi*n)+n*log10(n/e);
12         printf("%I64d\n",sum);
13     }
14     return 0;
15 }