Khóa học CTDL và GT

Bài 4.2: Giải phương trình đồng dư bằng nghịch đảo modulo

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của chúng ta! Sau khi đã làm quen với khái niệm đồng dư và một số phép toán cơ bản trong số học modular, hôm nay chúng ta sẽ đi sâu vào một ứng dụng quan trọng và thú vị: giải phương trình đồng dư tuyến tính. Cụ thể, chúng ta sẽ tập trung vào phương trình có dạng _ax ≡ b (mod m)_ và cách sử dụng nghịch đảo modulo để tìm ra nghiệm của nó.

Nếu bạn đã từng giải các phương trình tuyến tính trong số thực như ax = b, bạn biết rằng nếu a khác 0, nghiệm là x = b / a. Trong số học modular, khái niệm "chia" không tồn tại trực tiếp, nhưng chúng ta có một công cụ tương đương rất mạnh mẽ: nghịch đảo modulo.

Hãy cùng khám phá xem nghịch đảo modulo là gì, làm thế nào để tìm nó, và quan trọng nhất, làm thế nào để dùng nó "hóa giải" các phương trình đồng dư!

Nhắc Lại Cơ Bản về Đồng Dư

Trước khi đi tiếp, hãy đảm bảo chúng ta nắm vững khái niệm cốt lõi:

• Định nghĩa: Hai số nguyên a và b được gọi là đồng dư theo modulo m (ký hiệu a ≡ b (mod m)) nếu hiệu số a - b chia hết cho m. Nói cách khác, a và b có cùng số dư khi chia cho m.
• Phép toán: Các phép cộng, trừ, nhân đều hoạt động "tốt" với đồng dư. Ví dụ:
  • Nếu a ≡ b (mod m) và c ≡ d (mod m), thì a + c ≡ b + d (mod m).
  • Nếu a ≡ b (mod m) và c ≡ d (mod m), thì a * c ≡ b * d (mod m).

Tuy nhiên, phép chia thì không đơn giản như vậy. Ví dụ, 6 ≡ 2 (mod 4). Nếu "chia cả hai vế cho 2", ta có 3 ≡ 1 (mod 4), điều này là đúng. Nhưng nếu lấy 10 ≡ 4 (mod 6), và "chia cả hai vế cho 2", ta được 5 ≡ 2 (mod 6), điều này lại sai (5 - 2 = 3, không chia hết cho 6). Rõ ràng, chúng ta cần một cách tiếp cận khác cho "phép chia" trong thế giới modular.

Nghịch Đảo Modulo: "Phép Chia" Của Số Học Modular

Thay vì chia, chúng ta sử dụng nghịch đảo modulo. Trong số thực, nghịch đảo của a (khác 0) là a⁻¹ = 1/a, vì a * a⁻¹ = a * (1/a) = 1. Trong số học modular, chúng ta tìm một số tương tự:

• Định nghĩa: Một số nguyên x được gọi là nghịch đảo modulo của a theo modulo m nếu _a * x ≡ 1 (mod m)_. Nghịch đảo này thường được ký hiệu là a⁻¹.

Nếu a * x ≡ 1 (mod m), điều này có nghĩa là a * x - 1 chia hết cho m. Tức là, tồn tại một số nguyên k sao cho a * x - 1 = k * m. Sắp xếp lại, ta có phương trình _ax - mk = 1_. Đây là một dạng của phương trình Diophantine tuyến tính!

Khi nào Nghịch Đảo Modulo Tồn Tại?

Phương trình Diophantine ax + by = c có nghiệm nguyên x, y khi và chỉ khi gcd(a, b) chia hết c. Trong trường hợp của chúng ta, phương trình là ax + m(-k) = 1. Vậy, nghịch đảo x tồn tại khi và chỉ khi gcd(a, m) chia hết 1. Điều này chỉ xảy ra khi _gcd(a, m) = 1_.

Nói cách khác, nghịch đảo modulo của a theo modulo m chỉ tồn tại khi và chỉ khi a và m là nguyên tố cùng nhau (coprime).

Làm thế nào để Tìm Nghịch Đảo Modulo?

Khi gcd(a, m) = 1, chúng ta có thể tìm x (nghịch đảo của a mod m) từ phương trình ax + my = 1. Đây chính xác là công việc mà Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) làm!

Thuật toán Euclid mở rộng không chỉ tìm ước chung lớn nhất gcd(a, b) mà còn tìm các hệ số nguyên x và y sao cho ax + by = gcd(a, b). Áp dụng cho trường hợp của chúng ta với a và m, nó sẽ tìm x và y sao cho ax + my = gcd(a, m). Vì gcd(a, m) = 1, chúng ta sẽ có ax + my = 1. Số x mà thuật toán trả về chính là nghịch đảo của a theo modulo m. (Lưu ý: kết quả x có thể âm, chúng ta cần điều chỉnh nó để nằm trong khoảng [0, m-1] bằng cách cộng thêm m nếu cần và lấy modulo m).

Một cách khác để tìm nghịch đảo modulo khi m là số nguyên tố là sử dụng Định lý Fermat nhỏ: Nếu p là một số nguyên tố, thì với bất kỳ số nguyên a nào không chia hết cho p, ta có a^(p-1) ≡ 1 (mod p). Nhân cả hai vế với a⁻¹, ta được a⁻¹ * a^(p-1) ≡ a⁻¹ * 1 (mod p), suy ra a^(p-2) ≡ a⁻¹ (mod p). Do đó, nghịch đảo của a mod p là a^(p-2) mod p. Phương pháp này hiệu quả khi m là số nguyên tố, nhưng thuật toán Euclid mở rộng hoạt động cho bất kỳ m nào miễn là gcd(a, m) = 1.

Trong bài viết này, chúng ta sẽ tập trung vào phương pháp sử dụng Thuật toán Euclid mở rộng vì tính tổng quát của nó.

Giải Phương trình ax ≡ b (mod m)

Bây giờ chúng ta đã có công cụ nghịch đảo modulo, hãy xem cách áp dụng nó để giải ax ≡ b (mod m).

Trường hợp 1: gcd(a, m) = 1

Nếu a và m nguyên tố cùng nhau, thì nghịch đảo a⁻¹ (mod m) tồn tại và là duy nhất (trong khoảng [0, m-1]). Ta có phương trình: ax ≡ b (mod m)

Nhân cả hai vế với a⁻¹ (mod m): a⁻¹ * (ax) ≡ a⁻¹ * b (mod m) (a⁻¹ * a) * x ≡ a⁻¹ * b (mod m) 1 * x ≡ a⁻¹ * b (mod m) x ≡ a⁻¹ * b (mod m)

Vậy, nghiệm của phương trình là x ≡ (a⁻¹ * b) mod m. Phương trình này có duy nhất một nghiệm theo modulo m.

Trường hợp 2: gcd(a, m) = g > 1

Khi gcd(a, m) = g > 1, phương trình ax ≡ b (mod m) có thể có hoặc không có nghiệm.

• Điều kiện có nghiệm: Phương trình có nghiệm khi và chỉ khi b chia hết cho g = gcd(a, m). Tại sao? Vì ax ≡ b (mod m) tương đương với ax = b + km cho một số nguyên k. Sắp xếp lại: ax - km = b. Vế trái ax - km luôn chia hết cho g (vì a chia hết cho g và m chia hết cho g). Do đó, vế phải b cũng phải chia hết cho g.
• Nếu b không chia hết cho g: Phương trình vô nghiệm.

• Nếu b chia hết cho g: Phương trình có đúng g nghiệm không đồng dư theo modulo m. Để tìm các nghiệm này, chúng ta có thể chia cả ba thành phần của phương trình đồng dư cho g: (ax)/g ≡ (b)/g (mod m/g) (a/g)x ≡ (b/g) (mod m/g)

  Đặt a' = a/g, b' = b/g, m' = m/g. Phương trình trở thành: a'x ≡ b' (mod m')

  Bây giờ, gcd(a', m') = gcd(a/g, m/g) = gcd(a, m) / g = g / g = 1. Phương trình a'x ≡ b' (mod m') có dạng của Trường hợp 1, với gcd(a', m') = 1. Do đó, nó có duy nhất một nghiệm x₀ theo modulo m'. Ta tìm nghiệm x₀ này bằng cách nhân với nghịch đảo của a' theo modulo m': x₀ ≡ (a'⁻¹ * b') (mod m')

  Nghiệm x₀ này là duy nhất trong khoảng [0, m'-1]. Tuy nhiên, chúng ta cần nghiệm theo modulo m. Các nghiệm của phương trình ban đầu ax ≡ b (mod m) sẽ là: x ≡ x₀, x₀ + m', x₀ + 2m', ..., x₀ + (g-1)m' (mod m)

  Đây là g nghiệm không đồng dư theo modulo m.

Cài Đặt Bằng C++

Chúng ta cần các hàm sau:

1. Hàm tính GCD (Ước chung lớn nhất) - Thuật toán Euclid cơ bản.
2. Hàm tính GCD mở rộng và tìm hệ số x, y - Thuật toán Euclid mở rộng.
3. Hàm tìm nghịch đảo modulo sử dụng thuật toán Euclid mở rộng.
4. Hàm giải phương trình đồng dư ax ≡ b (mod m).

#include <iostream>
#include <vector>
#include <numeric> // For std::gcd in C++17, if available. Otherwise, implement manually.

// Hàm tính ước chung lớn nhất (GCD) bằng thuật toán Euclid
// Sử dụng std::gcd có sẵn trong C++17 trở lên
// Hoặc bạn có thể tự cài đặt:
long long custom_gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Hàm triển khai thuật toán Euclid mở rộng
// Tìm x, y sao cho a*x + b*y = gcd(a, b)
// Trả về gcd(a, b)
long long extendedGcd(long long a, long long b, long long &x, long long &y) {
    // Base case
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }

    long long x1, y1; // Để lưu kết quả từ lời gọi đệ quy
    long long gcd = extendedGcd(b % a, a, x1, y1);

    // Cập nhật x và y bằng kết quả từ lời gọi đệ quy
    x = y1 - (b / a) * x1;
    y = x1;

    return gcd;
}

// Hàm tìm nghịch đảo modulo của a theo mod m
// Trả về a^(-1) mod m nếu tồn tại, ngược lại trả về -1
long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extendedGcd(a, m, x, y);

    // Nếu gcd(a, m) != 1, nghịch đảo không tồn tại
    if (g != 1) {
        return -1; // Nghịch đảo không tồn tại
    } else {
        // Đảm bảo x dương và trong khoảng [0, m-1]
        return (x % m + m) % m;
    }
}

// Hàm giải phương trình đồng dư tuyến tính ax ≡ b (mod m)
// Trả về vector chứa các nghiệm (trong khoảng [0, m-1])
// Nếu vô nghiệm, trả về vector rỗng
std::vector<long long> solveLinearCongruence(long long a, long long b, long long m) {
    std::vector<long long> solutions;

    // Sử dụng std::gcd nếu có, ngược lại dùng custom_gcd
    long long g = custom_gcd(a, m);
    // long long g = std::gcd(a, m); // C++17+

    // Kiểm tra điều kiện có nghiệm
    if (b % g != 0) {
        // Vô nghiệm
        return solutions; // Trả về vector rỗng
    }

    // Nếu có nghiệm, chia cả phương trình cho g
    long long a_prime = a / g;
    long long b_prime = b / g;
    long long m_prime = m / g;

    // Giải phương trình đồng dư a'x ≡ b' (mod m')
    // Tìm nghịch đảo của a' theo mod m'
    long long inv_a_prime = modInverse(a_prime, m_prime);

    // Tính một nghiệm cụ thể cho phương trình rút gọn
    // x0 ≡ (b' * inv_a_prime) (mod m')
    long long x0 = (b_prime * inv_a_prime) % m_prime;
    if (x0 < 0) { // Đảm bảo x0 dương
        x0 += m_prime;
    }

    // Các nghiệm của phương trình ban đầu theo mod m là:
    // x0, x0 + m', x0 + 2m', ..., x0 + (g-1)m'
    for (int i = 0; i < g; ++i) {
        solutions.push_back(x0 + i * m_prime);
    }

    return solutions;
}

int main() {
    // Ví dụ 1: Trường hợp gcd(a, m) = 1 (có 1 nghiệm duy nhất)
    // 3x ≡ 7 (mod 10)
    // gcd(3, 10) = 1
    std::cout << "--- Vi du 1: 3x ≡ 7 (mod 10) ---" << std::endl;
    long long a1 = 3, b1 = 7, m1 = 10;
    std::vector<long long> sols1 = solveLinearCongruence(a1, b1, m1);
    if (sols1.empty()) {
        std::cout << "Phuong trinh vo nghiem." << std::endl;
    } else {
        std::cout << "Cac nghiem cua " << a1 << "x ≡ " << b1 << " (mod " << m1 << ") la:" << std::endl;
        for (long long sol : sols1) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "---------------------------------" << std::endl << std::endl;

    // Ví dụ 2: Trường hợp gcd(a, m) > 1 và gcd | b (có nhiều nghiệm)
    // 6x ≡ 12 (mod 18)
    // gcd(6, 18) = 6. 12 chia het cho 6. Co 6 nghiem.
    // Phuong trinh rut gon: (6/6)x ≡ (12/6) (mod 18/6)
    // 1x ≡ 2 (mod 3)
    // Nghiem cua rut gon: x0 = 2 (mod 3)
    // Cac nghiem mod 18: 2, 2 + 3, 2 + 2*3, ..., 2 + 5*3
    // Cac nghiem: 2, 5, 8, 11, 14, 17
    std::cout << "--- Vi du 2: 6x ≡ 12 (mod 18) ---" << std::endl;
    long long a2 = 6, b2 = 12, m2 = 18;
    std::vector<long long> sols2 = solveLinearCongruence(a2, b2, m2);
    if (sols2.empty()) {
        std::cout << "Phuong trinh vo nghiem." << std::endl;
    } else {
        std::cout << "Cac nghiem cua " << a2 << "x ≡ " << b2 << " (mod " << m2 << ") la:" << std::endl;
        for (long long sol : sols2) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "---------------------------------" << std::endl << std::endl;

    // Ví dụ 3: Trường hợp gcd(a, m) > 1 nhưng gcd không chia hết b (vô nghiệm)
    // 6x ≡ 10 (mod 18)
    // gcd(6, 18) = 6. 10 khong chia het cho 6. Vo nghiem.
    std::cout << "--- Vi du 3: 6x ≡ 10 (mod 18) ---" << std::endl;
    long long a3 = 6, b3 = 10, m3 = 18;
    std::vector<long long> sols3 = solveLinearCongruence(a3, b3, m3);
    if (sols3.empty()) {
        std::cout << "Phuong trinh vo nghiem." << std::endl;
    } else {
        std::cout << "Cac nghiem cua " << a3 << "x ≡ " << b3 << " (mod " << m3 << ") la:" << std::endl;
        for (long long sol : sols3) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "---------------------------------" << std::endl << std::endl;

     // Ví dụ 4: Một trường hợp đơn giản hơn với gcd > 1
    // 4x ≡ 8 (mod 6)
    // gcd(4, 6) = 2. 8 chia het cho 2. Co 2 nghiem.
    // Phuong trinh rut gon: (4/2)x ≡ (8/2) (mod 6/2)
    // 2x ≡ 4 (mod 3)
    // Nghich dao cua 2 mod 3 la 2 (vi 2*2 = 4 ≡ 1 mod 3)
    // Nghiem cua rut gon: x0 ≡ (4 * 2) mod 3 ≡ 8 mod 3 ≡ 2 (mod 3)
    // Cac nghiem mod 6: 2, 2 + 3
    // Cac nghiem: 2, 5
    std::cout << "--- Vi du 4: 4x ≡ 8 (mod 6) ---" << std::endl;
    long long a4 = 4, b4 = 8, m4 = 6;
    std::vector<long long> sols4 = solveLinearCongruence(a4, b4, m4);
    if (sols4.empty()) {
        std::cout << "Phuong trinh vo nghiem." << std::endl;
    } else {
        std::cout << "Cac nghiem cua " << a4 << "x ≡ " << b4 << " (mod " << m4 << ") la:" << std::endl;
        for (long long sol : sols4) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "---------------------------------" << std::endl << std::endl;


    return 0;
}

Giải thích Code C++

Chúng ta đã viết các hàm sau để giải phương trình đồng dư ax ≡ b (mod m):

1. custom_gcd(long long a, long long b):

   • Đây là hàm thực hiện Thuật toán Euclid cơ bản để tính ước chung lớn nhất của hai số a và b.
   • Nó sử dụng vòng lặp while (b) để liên tục thay thế a bằng b và b bằng số dư của a chia b cho đến khi b bằng 0.
   • Khi b bằng 0, giá trị hiện tại của a chính là GCD.
   • (Ghi chú: Nếu bạn dùng C++17 trở lên, bạn có thể dùng std::gcd từ thư viện <numeric> thay thế.)

2. extendedGcd(long long a, long long b, long long &x, long long &y):

   • Đây là hàm triển khai Thuật toán Euclid mở rộng một cách đệ quy.
   • Mục tiêu là tìm các số nguyên x và y sao cho ax + by = gcd(a, b).
   • Trường hợp cơ sở: Nếu a = 0, thì gcd(0, b) = b. Phương trình trở thành 0*x + b*y = b, ta có thể chọn x = 0 và y = 1. Hàm trả về b (là gcd) và gán x = 0, y = 1.
   • Bước đệ quy: Đối với a > 0, chúng ta sử dụng quan hệ của thuật toán Euclid: gcd(a, b) = gcd(b % a, a). Ta gọi đệ quy extendedGcd(b % a, a, x1, y1). Giả sử lời gọi đệ quy trả về gcd và tìm được x1, y1 sao cho (b % a)*x1 + a*y1 = gcd.
   • Ta biết b % a = b - (b / a) * a. Thay vào phương trình đệ quy: (b - (b / a) * a) * x1 + a * y1 = gcd b * x1 - (b / a) * a * x1 + a * y1 = gcd b * x1 + a * (y1 - (b / a) * x1) = gcd
   • So sánh với phương trình gốc a*x + b*y = gcd, ta thấy có thể chọn x = y1 - (b / a) * x1 và y = x1. Hàm cập nhật giá trị của các tham số tham chiếu x và y và trả về gcd.

3. modInverse(long long a, long long m):

   • Hàm này sử dụng extendedGcd để tìm nghịch đảo modulo.
   • Gọi extendedGcd(a, m, x, y) để tìm x, y sao cho ax + my = gcd(a, m).
   • g là giá trị trả về của extendedGcd, chính là gcd(a, m).
   • Kiểm tra nếu g != 1. Nếu đúng, nghịch đảo không tồn tại, hàm trả về -1.
   • Nếu g == 1, thì x là một trong các nghịch đảo của a mod m. Tuy nhiên, x có thể âm.
   • (x % m + m) % m là cách chuẩn để điều chỉnh một số nguyên x bất kỳ về một giá trị tương đương (đồng dư) trong khoảng [0, m-1] theo modulo m. Hàm trả về giá trị đã điều chỉnh này.

4. solveLinearCongruence(long long a, long long b, long long m):

   • Đây là hàm chính để giải phương trình ax ≡ b (mod m).
   • Đầu tiên, nó tính g = gcd(a, m).
   • Kiểm tra điều kiện có nghiệm: if (b % g != 0). Nếu b không chia hết cho g, phương trình vô nghiệm, trả về vector rỗng.
   • Nếu có nghiệm (b chia hết cho g), nó chia cả a, b, m cho g để nhận được phương trình rút gọn: a'x ≡ b' (mod m').
   • Tìm nghịch đảo của a' theo modulo m' bằng cách gọi modInverse(a_prime, m_prime).
   • Tính một nghiệm x0 cho phương trình rút gọn: x0 = (b_prime * inv_a_prime) % m_prime. Đảm bảo x0 dương bằng cách cộng thêm m_prime nếu cần.
   • Tạo một vector solutions để lưu trữ tất cả các nghiệm theo modulo m.
   • Các nghiệm là x0, x0 + m', x0 + 2*m', ..., x0 + (g-1)*m'. Thêm g nghiệm này vào vector solutions.
   • Trả về vector solutions.

Hàm main cung cấp các ví dụ minh họa cho cả ba trường hợp: có một nghiệm, có nhiều nghiệm, và vô nghiệm, giúp bạn dễ dàng kiểm tra và hiểu cách sử dụng hàm solveLinearCongruence.

Bài tập ví dụ:

Phản ứng dây chuyền

Trong một buổi thực tập tại ngân hàng, FullHouse Dev được giao một bài toán thú vị về chuỗi phản ứng trong hệ thống giao dịch. Họ cần tính toán số lượng giao dịch tại mỗi nút mạng dựa trên một quy luật đặc biệt.

Bài toán

Có vô số phòng được đánh số từ 0, trong đó phòng số \(K\) được kết nối với phòng số \(K-1\). Ban đầu, có \(X\) phần tử ở phòng số 0. Số phần tử trong phòng \(K\) bằng \(K\) lần số phần tử trong phòng \(K-1\). FullHouse Dev cần tìm số phần tử trong phòng thứ \(N\).

Lưu ý: Không thể tính số phần tử trong phòng \(K\) nếu chưa tính được số phần tử trong phòng \(K-1\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Mỗi test case gồm hai số nguyên \(N\) và \(X\) cách nhau bởi dấu cách

OUTPUT FORMAT:

• Với mỗi test case, in ra số phần tử trong phòng thứ \(N\)
• Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^6+3\)

Ràng buộc:

• \(1 \leq T \leq 10^5\)

Subtask 1: (20 điểm)

• \(1 \leq N, X \leq 10^5\)

Subtask 2: (80 điểm)

• \(1 \leq N, X \leq 10^{18}\)

Ví dụ

INPUT

2
1 3
2 1

OUTPUT

3
2

Giải thích

• Test case 1: Ban đầu có 3 phần tử. Ở phòng \(K=1\), số phần tử là \(1*3 = 3\).
• Test case 2: Ban đầu có 1 phần tử. Ở phòng \(K=1\), số phần tử là \(1*1 = 1\). Ở phòng \(K=2\), số phần tử là \(2*1 = 2\). Tuyệt vời! Đây là hướng dẫn giải bài "Phản ứng dây chuyền" một cách ngắn gọn, tập trung vào logic và các điểm cần lưu ý:

1. Tìm công thức: Quan sát quy luật E_K = K * E_{K-1} với E_0 = X. Mở rộng dần:

   • E_1 = 1 * E_0 = 1 * X
   • E_2 = 2 * E_1 = 2 * (1 * X) = 2 * 1 * X
   • E_3 = 3 * E_2 = 3 * (2 * 1 * X) = 3 * 2 * 1 * X
   • Tổng quát, số phần tử trong phòng N là E_N = N * (N-1) * ... * 2 * 1 * X. Công thức này chính là E_N = N! * X.

2. Tính modulo: Bài toán yêu cầu in kết quả modulo M = 10^6 + 3. Ta cần tính (N! * X) % M. Sử dụng tính chất (a * b) % M = ((a % M) * (b % M)) % M. Vậy, ta cần tính ((N! % M) * (X % M)) % M.

3. Xử lý X % M: X có thể rất lớn (10^18), nên cần đọc X bằng kiểu dữ liệu 64-bit (ví dụ: long long trong C++). Phép tính X % M đơn giản là lấy phần dư của X khi chia cho M.

4. Xử lý N! % M với N lớn: Đây là phần quan trọng nhất do N cũng có thể rất lớn (10^18).

   • Nhận xét về Modulo M = 10^6 + 3: Đây là một số nguyên tố.
   • Trường hợp N >= M: Nếu N lớn hơn hoặc bằng số nguyên tố M, thì trong tích N! = 1 * 2 * ... * M * ... * N, có thừa số M. Do đó, N! sẽ chia hết cho M. Khi đó, N! % M = 0.
   • Trường hợp N < M: Nếu N nhỏ hơn M, ta không thể áp dụng nhận xét trên ngay lập tức. Cần tính N! % M bằng cách lặp từ 1 đến N. Khi tính tích, áp dụng phép modulo sau mỗi lần nhân để tránh tràn số: fact_mod_M = (fact_mod_M * i) % M cho i từ 1 đến N. Vì N < M = 10^6 + 3, vòng lặp này sẽ chạy tối đa khoảng 1 triệu lần, đủ nhanh cho các ràng buộc của Subtask 2.

5. Kết hợp kết quả:

   • Đọc N và X bằng kiểu dữ liệu 64-bit (long long).
   • Đặt M = 10^6 + 3.
   • Tính X_mod_M = X % M.
   • Kiểm tra nếu N >= M: Kết quả là 0.
   • Nếu N < M:
     • Tính N_fact_mod_M = 1.
     • Vòng lặp i từ 1 đến N: N_fact_mod_M = (N_fact_mod_M * i) % M.
     • Kết quả cuối cùng là (N_fact_mod_M * X_mod_M) % M. Chú ý kết quả phép nhân trước khi lấy modulo cuối cùng có thể lớn, nên cũng cần dùng kiểu 64-bit hoặc ép kiểu trước khi nhân.

Làm thêm nhiều bài tập miễn phí tại đây