[大數] C 語言大數演算法 - 階乘問題 @ Edison.X. Blog

[1] 算有幾位數

嚴格講起，這是個假大數問題。

可用斯特靈公式逼近，但拿到的是一個近似值。要細算的話推導如下。

n! = n * (n-1) * (n-2) * .... * 2 * 1 ，算位數取 log10，

log10(n!) = log10( n * (n-1) * (n-2) * .... * 2 * 1 ) ，

log10(n!) = log10(n) + log10(n-1) + log10(n-2) + .... + log10(2) + log10(1) ，

最後結果出來再取 ceil 。

雖浮點數有誤差，但有效是 53 位數，應付到幾十萬階乘是絕對足夠 (速度變慢倒是真的)

[2] 精算值 - 暴力法

一樣用大數去做，先放上暴力法

Code Snippet
// --------------------------------------
// 精算 n! 之值, 傳回有幾位數 , slow
int fact(int n, int * Big, int size)
{
    int i, j, dig=1, carry=0;
    int mini, pwr, num;
    
    if(n<0) {Big[0]=0; return -1;}
    else if(n==0 || n==1) {Big[0]=1; return 1;}
    
    Big[0] = 1;
    for(i=2 ; i<=n; ++i){
 
        // 進行大數乘法
        if(size < dig) mini = size;
        else mini = dig;
 
        for(carry =j=0 ; j<mini; ++j) {
            Big[j] = carry + Big[j] * i;
            carry  = Big[j] / BIG_CAP;
            Big[j]%=BIG_CAP;
        }
        // 調進位
        while(carry && j<size){
            Big[j] = carry % BIG_CAP;
            carry /= BIG_CAP;
            ++j;
        }
        dig=j;
    }
    // 計算有幾個位數
    dig = (j-1)*BIG_LEN;
    for(num=Big[j-1]; num ; num/=10) ++dig;
    return dig;
}

注意中間使用的 dig 計算，拿來加快乘法速度。試過，用萬進位可行。

[4] 精算值 - 質因數分解

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2，把每個數做質因數分解，得到，

10! = 2^8 * 3^4 * 5^2 * 7，接下來就好辦了。

找一個階乘的質因式分解，其實有技巧，但需要較大的空間(一般題目應該都算夠用，目前看過找較大的是上萬)。一開始最好先建質數表，可以普通篩法或線性篩法都行 ( 幾十萬以內都很快)。篩法得到質數為 {2,3,5,7} 接著...

(1) 一開始拿質數 2 出來，

i = 1 , cnt = 0;
i = i * 2 = 2 , 10 / 2 = 5 , cnt+=5, cnt=5
i = i * 2 = 4 , 10 / 4 = 2 , cnt+=2, cnt=7
i = i * 2 = 8 , 10 / 8 = 1, cnt+=1 , cnt=8

(2) 再拿出質數 3 出來

i = 1 , cnt = 0;
i = i * 3 = 3 , 10 / 3 = 3 , cnt+=3, cnt=3
i = i * 3 = 9 , 10 / 9 = 1 , cnt+=1, cnt=4
i = i * 3 = 27 , 結束

其他拿質數 5、質數 7 都一樣。另外可以額外處理地方是在質數 7 。

因為是 10!，10/2 = 5，而 7 > 5，故可以判定，7 一定只有一個，就是自己，其它的絕不可能再分解下去 (很簡單的數論應用而已)。換比較通用的講法是：在求 n 階乘，做上述動作時，只要做到 n/2 便可，其它大於 n/2 的全都乘上去就行了。

fast-power 有個地方要注意，由於出來的結果可能會 overflow，故建議最好事先判斷有沒有可能會 ov。沒 ov 的話用大數做 fast_power 有點浪費，有 ov 就一定得用大數做 fast-power。

再來是看想不想進一步優化。再以 10! 為例。10! = 2^8 * 3^4 * 5^2 * 7^1，考慮前兩項就好，(2^8) * (3^4) = (6^4) * (2^4)，效果略有所不同。拆法有很多種 (特別注意到這個例子的次方剛好是 8 4 2 1 )，考慮溢位、速度之間做取捨之衡量，要設計好不容易。其他的不再贅述。

[5] 判斷尾數有幾個零

這是個假大數問題。

要構成一個 0 ，一定要有 2/5 同時存在相乘，如 8 * 5 = 2*2*2 *5 ，只能取出 1 對 2/5 出來，所以只有一個零；又如 16 * 125 = 2^4 * 5^3，可以取出 3 對出來，所以尾數有 3 個零。

然後很明顯的一點是，[1,n] 裡面，可以被 2 分解的個數，一定比可以比 5 分解的個數還多。

再來是，像 25 可以再被多提一個 5 出來、125 又可以再多提一個 5 出來，所以最後就是在算有幾個數字可以被 5 / 25 / 125 / 625 / .... 分解，總合就是答案。

Code Snippet
#include <stdio.h>
 
int fact_tail_zero(int n)
{
    int ret=0;
    while(n/=5) ret+=n;
    return ret;
}
 
int main()
{
    int x;
    while(scanf("%d", &x)==1)
        printf("tail zero : %d\n", fact_tail_zero(x));
    return 0;
}