Tích N giai thừa đầu tiên trong C++

Cho số N. Nhiệm vụ: tính tích của N giai thừa đầu tiên: 1! × 2! × 3! × ... × N! modulo 1.000.000.007.

Ràng buộc: 1 ≤ N ≤ 10⁶.

Ví dụ 1

Input – n = 3

Output – 12

Giải thích: 1! × 2! × 3! = 1 × 2 × 6 = 12.

Ví dụ 2

Input – n = 9

Output – 27

Giải thích: 1!×2!×...×9! mod (1e9+7) = 27.

Thuật toán

1. Khởi tạo fact = 1, product = 1.
2. Với i = 1..N:
   • fact = fact × i % MOD (tính i! từ (i-1)!)
   • product = product × fact % MOD
3. Trả về product.

Cần hàm mulmod để nhân an toàn tránh tràn 64-bit khi MOD ~ 1e9 (long long đủ chứa 1e18, nhưng an toàn hơn dùng mulmod).

Ví dụ code

#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;

long long mulmod(long long a, long long b) {
    return (a * b) % MOD; // long long đủ cho (1e9)^2 < 2^63
}

long long productOfFactorials(int n) {
    long long fact = 1, prod = 1;
    for (int i = 1; i <= n; i++) {
        fact = mulmod(fact, i);
        prod = mulmod(prod, fact);
        if (prod == 0) return 0; // Đã chia hết MOD
    }
    return prod;
}

int main() {
    int n = 3;
    cout << productOfFactorials(n) << endl;
    return 0;
}

Kết quả

12

Lưu ý: Code gốc dùng mulmod phức tạp kiểu binary multiplication. Với MOD = 1e9+7 < 2³¹, long long (64-bit) chứa được tích 2 số < MOD, nên nhân trực tiếp an toàn. Code trên đơn giản hóa.

Độ phức tạp: O(N). Với N=10⁶ chạy rất nhanh.