« CÂU HỎI Tin học · Lớp $10$ $...$

Bản chất toán học

Giả sử ta có hai số nguyên dương $A$ và $B$. Không mất tính tổng quát, giả sử $A \le B$.

Khi đó, theo định nghĩa của giai thừa:

$A! = 1 \cdot 2 \cdot 3 \dots A$

$B! = 1 \cdot 2 \cdot 3 \dots A \cdot (A+1) \dots B$

Dễ dàng nhận thấy rằng $B!$ hoàn toàn chia hết cho $A!$ vì trong tích của $B!$ đã chứa sẵn toàn bộ tích của $A!$. Nói cách khác, $A!$ chính là một ước số của $B!$.

Vì $A!$ vừa là ước của chính nó, vừa là ước của $B!$, nên ước số chung lớn nhất của hai số này chính là số nhỏ hơn trong hai giai thừa.

Công thức tổng quát:

$\text{ƯCLN}(A!, B!) = \min(A, B)!$

Giải thuật lập trình

Do đó, thuật toán để giải bài toán này cực kỳ tối ưu:

So sánh hai số $A$ và $B$ để tìm số nhỏ hơn (gọi là $N = \min(A, B)$).

Kết quả chính là $N!$.

Tuy nhiên, bạn cần lưu ý về cách hiển thị kết quả tùy thuộc vào yêu cầu của đề bài:

Nếu đề bài yêu cầu in ra giá trị cụ thể: Vì $A, B \le 10^9$ nên thông thường đề bài sẽ yêu cầu chia lấy dư cho một số nguyên tố lớn (ví dụ: $10^9 + 7$), lúc này bạn chỉ cần dùng một vòng lặp từ $1$ đến $N$ để tính giai thừa lấy dư.

Nếu đề bài chỉ cần dạng thu gọn: Bạn chỉ cần in ra chuỗi kết quả có định dạng N! (ví dụ: 5!).

Đoạn code minh họa (C++)

Dưới đây là cấu trúc code xử lý trong trường hợp tính kết quả theo modulo $10^9+7$:

C++

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long A, B;
    cin >> A >> B;
    
    // Tìm số nhỏ hơn
    long long N = min(A, B);
    
    // Tính N! theo modulo 10^9 + 7 (nếu đề bài yêu cầu giá trị cụ thể)
    long long mod = 1e9 + 7;
    long long ans = 1;
    
    for (int i = 1; i <= N; i++) {
        ans = (ans * i) % mod;
    }
    
    cout << ans << endl;
    
    return 0;
}

Độ phức tạp thuật toán: $\mathcal{O}(\min(A, B))$, hoàn toàn chạy tốt trong giới hạn thời gian nếu $\min(A, B) \le 10^7$. Trường hợp dữ liệu lớn hơn và không có modulo, thông thường kết quả đầu ra sẽ được yêu cầu giữ nguyên dưới dạng ký hiệu là min(A, B)!.