Hướng dẫn giải

Cho hai số nguyên dương a và b, tính ước chung lớn nhất của a! và b!. Biết min(a, b) không vượt quá 20.

Cách làm

Với hai số nguyên dương, ước chung lớn nhất của a! và b! luôn bằng giai thừa của số nhỏ hơn: ~\text{UCLN}(a!, b!) = \min(a, b)!~. Lý do là số nhỏ hơn đã là một thừa số của cả hai giai thừa, và không có ước chung nào lớn hơn.

Vì vậy chương trình chỉ cần lấy m = min(a, b) rồi tính m! bằng vòng lặp nhân dồn từ 1 đến m.

Bẫy cần nhớ: giai thừa tăng rất nhanh, 20! khoảng 2,4 · 10^18 nên phải dùng long long. Với int kết quả sẽ bị tràn số.

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("gcd.inp", "r", stdin);
    freopen("gcd.out", "w", stdout);
    long long a, b;
    cin >> a >> b;
    // UCLN(a!, b!) = min(a, b)!  (vi min(a,b) <= 20 nen ket qua nho hon 2^63)
    long long m = min(a, b);
    long long giaithua = 1;
    for (long long i = 1; i <= m; i++) {
        giaithua = giaithua * i;
    }
    cout << giaithua << "\n";
    return 0;
}