描述

N！階乘是一個非常大的數，大家都知道計算公式是N!=N*(N-1）······*2*1.現在你的任務是計算出N！的位數有多少（十進制）？

輸入

首行輸入n，表示有多少組測試數據(n<10)
隨后n行每行輸入一組測試數據 N( 0 < N < 1000000 )

輸出

對于每個數N，輸出N!的（十進制）位數。

樣例輸入

3

1

3

32000

樣例輸出

1

1

130271

/*    NYOJ69 階乘數位長度

 *    方法一:

 *    可設想n!的結果是不大于10的M次冪的數,即n!<=10^M(10的M次方),則不小于M的最小整數就是 n!的位數，對

 *    該式兩邊取對數，有 M =log10^n! 即：M = log10^1+log10^2+log10^3...+log10^n 循環求和,就能算得M值，

 *    該M是n!的精確位數。當n比較大的時候，這種方法方法需要花費很多的時間。

 *

 *    方法二:

 *    利用斯特林（Stirling）公式的進行求解。下面是推導得到的公式：

 *    res=(long)( (log10(sqrt(4.0*acos(0.0)*n)) + n*(log10(n)-log10(exp(1.0)))) + 1 );

 *    當n=1的時候，上面的公式不適用，所以要單獨處理n=1的情況！

 *    有關斯特林（Stirling）公式及其相關推導，這里就不進行詳細描述，有興趣的話可看這里。

 *    這種方法速度很快就可以得到結果。詳細證明如下：

 *    http://episte.math.ntu.edu.tw/articles/mm/mm_17_2_05/index.html

*/

#include<iostream>

#include <cmath>

using namespace std;

int normal(double n)

{

    double x=;

    while(n)

    {

        x +=log10(n);

        n--;

    }

    return (int)x+;

}

long stirling(double n)

{

    long x=;

    if( n == )

        x = ;

    else

    {

        x = (long)( (log10(sqrt(4.0*acos(0.0)*n)) + n*(log10(n)-log10(exp(1.0)))) +  );

    }

    return x;

}

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        int x;

        cin>>x;

        cout<<stirling(x)<<endl;

    }

    return ;

}                

總結

以上是生活随笔為你收集整理的ACM 阶乘数位数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。