萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

階乘算法全景:高精度計算、數論應用與 C++ 實現

一、高精度階乘計算

1. 小階乘 (n ≤ 12) 直接遞歸

long long fact_small(int n) {
    return (n <= 1) ? 1 : n * fact_small(n - 1);
}

12! = 479001600 仍在 32 位有符號範圍內;13! 溢出。

2. 大階乘:模擬手工乘法 (數組存儲十進制位)

數組 a[0] 存長度,a[1] 存個位,a[2] 存十位... (低位在前)。

void multiply(int a[], int b) {  // a *= b
    int carry = 0;
    for (int i = 1; i <= a[0]; ++i) {
        int prod = a[i] * b + carry;
        a[i] = prod % 10;
        carry = prod / 10;
    }
    while (carry) {
        a[++a[0]] = carry % 10;
        carry /= 10;
    }
}

void big_factorial(int n, int result[]) {
    result[0] = 1; result[1] = 1; // 1! = 1
    for (int i = 2; i <= n; ++i) multiply(result, i);
}

3. 輸出輔助

void print_big(const int a[]) {
    for (int i = a[0]; i >= 1; --i) std::cout << a[i];
    std::cout << '\n';
}

二、數論相關經典問題

(1) 階乘末尾第一個非零數字

核心觀察:末尾 0 來自因子 2×5,2 的個數遠超 5。去除所有因子 5 並同步移除等量因子 2,剩餘乘積模 10 即為答案。
規律:5 ≡ 8 (mod 10) 當配對因子 2 時,故可將每個因子 5 視為 8 參與乘積。因子 5 的個數模 4 循環 (2,6,8,4)。

int last_nonzero_digit(int n) {
    static const int res[5][4] = {
        {0,0,0,0},
        {2,6,8,4},  // 1 個因子5
        {4,2,6,8},  // 2 個
        {6,8,4,2},  // 3 個
        {8,4,2,6}   // 4 個
    };
    int nonzero = 1, five = 0;
    for (int i = 2; i <= n; ++i) {
        int t = i;
        while (t % 5 == 0) { t /= 5; five = (five + 1) % 4; }
        while (t % 2 == 0 && five) { t /= 2; five = (five + 3) % 4; } // 移除配對的2
        nonzero = (nonzero * t) % 10;
        if (five) nonzero = res[nonzero/2][five]; // nonzero 為偶數
    }
    return nonzero;
}

(2) 階乘末尾 0 的個數

等價於統計 1~n 中因子 5 的總個數:

int trailing_zeros(int n) {
    int cnt = 0;
    while (n) { n /= 5; cnt += n; }
    return cnt;
}

(3) 階乘左側第二位數字 (最高兩位)

用 double 維持科學記數法有效數字:

int second_digit(int n) {
    double val = 1;
    for (int i = 2; i <= n; ++i) {
        val *= i;
        while (val >= 100) val /= 10; // 保持兩位有效數字
    }
    return static_cast<int>(val) % 10;
}

(4) 判斷 m 是否整除 n!

素因子分解法:對 m 的每個質因子 p,比較 n! 中 p 的指數 (Legendre 公式) 是否 ≥ m 中的指數。

bool divides_factorial(int m, int n) {
    if (m == 0) return false;
    if (n >= m) return true;
    int mm = m;
    for (int p = 2; p * p <= mm; ++p) {
        if (mm % p) continue;
        int cnt_m = 0;
        while (mm % p == 0) { mm /= p; ++cnt_m; }
        int cnt_n = 0, t = n;
        while (t) { t /= p; cnt_n += t; }
        if (cnt_n < cnt_m) return false;
    }
    if (mm > 1) { // 剩餘大質因子
        int cnt_n = 0, t = n;
        while (t) { t /= mm; cnt_n += t; }
        if (cnt_n < 1) return false;
    }
    return true;
}

(5) 數字 N 能否表示為不同階乘之和 (0!~9!)

可用數字僅 10 個,DFS 全搜索即可 (2^10 = 1024 種組合)。

bool can_sum_factorial(int N) {
    int fact[10]; fact[0] = 1;
    for (int i = 1; i < 10; ++i) fact[i] = fact[i-1] * i;

    std::vector<bool> reachable(3628800 + 1, false); // 9! = 362880
    std::function<void(int,int)> dfs = [&](int idx, int sum) {
        if (idx == 10) { reachable[sum] = true; return; }
        dfs(idx+1, sum);
        dfs(idx+1, sum + fact[idx]);
    };
    dfs(0, 0);
    return N < reachable.size() && reachable[N];
}

三、工程化建議

  • 高精度階乘預計算表 (至 1000! 等) 存儲為字符串/十進制數組,查詢 O(1)。
  • 數論題目善用 Legendre 公式 統計質因子指數:e_p(n!) = Σ floor(n/p^k)。
  • 競賽模板建議封裝 BigInteger 類 (或用 boost::multiprecision::cpp_int),避免重複造輪子。
copyright © 萬盛學電腦網 all rights reserved