10.3K 776 120

Đã đăng vào thg 1 30, 8:00 SA 5 phút đọc

683

Số học đồng dư (Phần 2): Phương trình đồng dư tuyến tính

Trong bài viết này, chúng ta sẽ cùng thảo luận về phương pháp giải của phương trình đồng dư tuyến tính - một dạng phương trình khá quen thuộc trong số học đồng dư nhưng lại không được đề cập trong chương trình Toán cấp THCS - THPT. Đó là phương trình có dạng:

$a.x \equiv b \ (\text{mod } n) \ (1)$

Mặc dù chỉ phổ biến trong các chuyên đề HSG Toán, nhưng trong Tin học thì phương trình này lại khá thú vị và có thể áp dụng để giải quyết một số bài toán trong lập trình thi đấu. Vấn đề đặt ra là cần tìm các nghiệm $x$ của phương trình thuộc đoạn $[0, n - 1]$ (bởi vì dễ dàng nhận thấy rằng, nếu như phương trình trên tồn tại nghiệm $x_0$ thì nó sẽ có vô số nghiệm trên trục số nguyên với khoảng cách là $n \times k$ giữa các nghiệm, với $k$ là số nguyên bất kì).

Ta sẽ phát biểu lại bài toán đầy đủ như sau: Cho phương trình đồng dư tuyến tính:

$a.x \equiv b \ (\text{mod } n) \ (1)$

Yêu cầu: Giải phương trình trên và tìm ra các nghiệm $x$ của phương trình thuộc đoạn $[0, n - 1]?$

Input:

Một dòng duy nhất chứa ba số nguyên dương $a, b, n$ .

Ràng buộc:

$1 \le a, b, n \le 10^9$ .

Output:

In ra tất cả các nghiệm của phương trình theo thứ tự từ nhỏ tới lớn. Nếu phương trình vô nghiệm thì in ra No solution.

Sample Input 1:

3 6 10

Sample Output 1:

Sample Input 2:

2 1 4

Sample Output 2:

No solution

Phương pháp giải

Trường hợp cơ sở

Xét trường hợp đơn giản nhất của phương trình là khi $n$ và $a$ là hai số nguyên tố cùng nhau, tức là $\text{GCD}(a, n) = 1$ . Khi đó, ta sẽ giải phương trình bằng cách tìm nghịch đảo modulo $n$ của $a,$ (tạm gọi là $a^{-1}$ ) rồi nhân cả hai vế của phương trình $(1)$ với nghịch đảo đó:

$x = b.a^{-1} \ (\text{mod } n)$

Hiển nhiên ta sẽ thu được nghiệm $x$ của bài toán, và nghiệm này là nghiệm duy nhất.

Để tìm được giá trị $a^{-1},$ do ở phương trình này $n$ không phải luôn luôn là số nguyên tố, nên các bạn buộc phải sử dụng Giải thuật Euclid mở rộng. Bài viết về chuyên đề này các bạn đọc lại tại <i>đây.</i>

Trường hợp tổng quát

Bây giờ, xét trường hợp $a$ và $n$ không nguyên tố cùng nhau, tức là $\text{GCD}(a, n) \ne 1$ . Trong trường hợp này, sẽ có đôi lúc phương trình xảy ra vô nghiệm, chẳng hạn như $2.x \equiv 1 \ (\text{mod } 4)$ là một phương trình vô nghiệm.

Đặt $g = \text{GCD}(a, n);$ trong trường hợp này tất nhiên $g > 1$ .

Sẽ có hai trường hợp xảy ra:

Trường hợp 1: $b$ không chia hết cho $g$ . Trường hợp này phương trình sẽ vô nghiệm. Chứng minh: Với mọi giá trị nguyên của $x,$ vế phải của phương trình $(1)$ là $a.x$ luôn luôn chia hết cho $g,$ nhưng vế trái $b$ lại không chia hết cho $g$ . Từ đó xảy ra mâu thuẫn, vì thế phương trình vô nghiệm.
Trường hợp 2: $b$ chia hết cho $g$ . Ta chia cả hai vế của phương trình ban đầu cho $g,$ được phương trình mới dưới đây:

$a_1.x \equiv b_1 \ (\text{mod } n_1)$
với $a_1 = \frac{a}{g}, b_1 = \frac{b}{g}, n_1 = \frac{n}{g}$

Đến đây, chắc chắn $a_1$ và $n_1$ đã trở thành hai số nguyên tố cùng nhau, do chúng ta đã chia cả hai số cho ước chung lớn nhất của chúng. Phương trình sẽ lại quy về dạng đơn giản với nghiệm là:

$x_1 = b_1 \times a_1^{-1} \ (\text{mod } n_1)$
Nghiệm này sẽ là nghiệm nhỏ nhất của phương trình trên đoạn $[0, n - 1]$ .

Tìm tất cả các nghiệm của phương trình

Đến đây, sau khi đã biết cách tìm ra nghiệm nhỏ nhất $x_1,$ thì việc tìm ra các nghiệm còn lại khá đơn giản. Có thể chứng minh được rằng, phương trình đã cho có đúng $g$ nghiệm trên đoạn $[0, n - 1]$ theo công thức:

$x_i = (x_1 + i \times n_1) \ (\text{mod } n); \forall i: 0 \le i < g$

Một vòng lặp là đủ để tìm ra tất cả các nghiệm này!

Cài đặt

#include <bits/stdc++.h>

using namespace std;

// Giải thuật Euclid mở rộng, tìm cặp nghiệm nguyên (x, y) thỏa mãn 
// phương trình ax + by = GCD(a, b).
void extended_euclid(int a, int b, int &x, int &y, int &g)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        g = a;
    }
    else
    {
        extended_euclid(b, a % b, x, y, g);
        int t = x;
        x = y;
        y = t - (a / b) * y;
    }
}

main()
{
    int a, b, n;
    cin >> a >> b >> n;

    int x, y, g;
    extended_euclid(a, n, x, y, g);

    if (g == 1)
    {
        int inv_a = (x + n) % n;
        cout << ((b % n) * inv_a) % n;
    }
    else
    {
        if (b % g != 0)
            cout << "No solution";
        else
        {
            a /= g;
            b /= g;
            n /= g;

            extended_euclid(a, n, x, y, g);

            int inv_a = (x + n) % n;
            int x1 = ((b % n) * inv_a) % n;
            for (int i = 0; i < g; ++i)
                cout << (x1 + i * n) % n << endl;
        }
    }

    return 0;
}

Bài toán ví dụ

Đề bài

Có $n$ chiếc ghế sắp xếp vòng tròn. Có đúng một chiếc ghế trong vòng tròn được gọi là ghế đẹp.

Ban đầu, Hà đang ngồi sẵn tại chiếc ghế đẹp. Sau đó, Hà đứng lên và di chuyển theo chiều kim đồng hồ, rồi ngồi vào chiếc ghế liền kề thứ $s$ theo hướng di chuyển.

Sau đó, Hà sẽ tiếp tục thực hiện di chuyển sau đây: Xuất phát từ chiếc ghế đang ngồi, đứng lên và di chuyển theo chiều kim đồng hồ, rồi ngồi vào chiếc ghế liền kề thứ $k$ theo hướng di chuyển. Hà có thể không thực hiện di chuyển nào.

Yêu cầu: Hãy xác định xem, Hà có thể quay trở lại ngồi vào chiếc ghế đẹp sau khi thực hiện một số lần di chuyển hay không?

Input:

Dòng đầu chứa số $T$ là số lượng test cases.
$T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $n, s, k$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \le T \le 100$ .
$2 \le n \le 10^9$ .
$1 \le s < N$ .
$1 \le k \le 10^9$ .

Output:

In ra số thứ tự của thao tác di chuyển đầu tiên mà sau khi thực hiện thao tác đó, Hà quay lại ngồi lên chiếc ghế đẹp. Nếu như Hà không thể ngồi lại vào ghế đẹp, in ra $-1$ . Kết quả của mỗi test case được in trên một dòng.

Sample Input:

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

Sample Output:

Giải thích:

Ở test case đầu tiên, giả sử ghế đẹp là ghế thứ $x$ , lúc đầu Hà đang ở ghế thứ $x+4$ . Sau $2$ thao tác di chuyển, Hà tới ghế thứ $x+4+3+3$ là $x+10$ , chính là $x$ (Vì di chuyển theo vòng tròn nên cứ sau $n$ ghế thì quay lại vị trí ban đầu).

Ý tưởng

Giả sử Hà thực hiện thao tác di chuyển thứ hai $x$ lần. Vậy nếu như Hà muốn quay trở lại đúng vị trí ban đầu, thì $s + x.k$ phải chia hết cho $n$ . Nói cách khác, phương trình dưới đây phải có nghiệm:

$s + x.k \equiv 0 \ (\text{mod } n)$

$\Leftrightarrow x.k \equiv n - s \ (\text{mod } n)$

Tới đây bài toán quy về việc giải phương trình đồng dư tuyến tính với $a = k, b = n - s$ . Mà đề bài lại yêu cầu tìm ra nghiệm $x$ nhỏ nhất, nên cách giải ở trên đã hướng dẫn sẽ cho ra luôn kết quả đúng.

Độ phức tạp: $O\big(\log(n)\big)$ .

Cài đặt

#include <bits/stdc++.h>
#define int long long
#define task "throne."

using namespace std;

void enter(int &n, int &s, int &k)
{
    cin >> n >> s >> k;
}

// Giải thuật Euclid mở rộng, tìm cặp nghiệm nguyên (x, y) thỏa mãn ax + by = GCD(a, b).
void extended_euclid(int a, int b, int &x, int &y, int &g)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        g = a;
    }
    else
    {
        extended_euclid(b, a % b, x, y, g);
        int t = x;
        x = y;
        y = t - (a / b) * y;
    }
}

// Giải phương trình đồng dư tuyến tính: x.K đồng dư (N - S) (mod N).
void query(int n, int s, int k)
{
    int x, y, g;
    extended_euclid(k, n, x, y, g);

    // GCD(k, n) = 1 thì phương trình có nghiệm duy nhất là x = (N - S) * K^(-1) (mod N).
    if (g == 1)
    {
        int k_inv = (x + n) % n;
        cout << (((n - s) % n) * k_inv) % n << endl;
    }
    // GCD(k, n) != 1 thì xử lý hai trường hợp.
    else
    {
        // Nếu (n - s) không chia hết cho gcd(k, n) thì phương trình vô nghiệm.
        if ((n - s) % g != 0)
            cout << -1 << endl;
        // Ngược lại gán k1 = k / g, n1 = n / g, p = (n - s) / g với g = gcd(k, n).
        // rồi sử dụng công thức giống như trường hợp gcd(k, n) = 1 với (k1, n1, p).
        else
        {
            // Thực hiện lại giải thuật Euclid mở rộng với bộ ba mới.
            int k1 = k / g, n1 = n / g, p = (n - s) / g;
            extended_euclid(k1, n1, x, y, g);

            // Áp dụng đúng công thức cũ để tìm ra nghiệm của phương trình.
            int k_inv = (x + n1) % n1;

            cout << (p % n1 * k_inv) % n1 << endl;
        }
    }
}

void solution(int &q)
{
    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int n, s, k;

        enter(n, s, k);
        query(n, s, k);
    }
}

main()
{
    //freopen(task"inp", "r", stdin);
    //freopen(task"out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    solution(q);

    return 0;
}