Editorial

Mô tả bài toán

Cho hai số nguyên dương a và b. Nhiệm vụ của bài toán là tìm nghiệm nguyên dương nhỏ nhất x sao cho:

\[ a \cdot x \equiv 1 \pmod{b} \]

Điều này có nghĩa là \(a \cdot x\) chia cho \(b\) dư 1. Dữ liệu đầu vào được đảm bảo có luôn tồn tại nghiệm (tức là \(a\) và \(b\) là coprime, hay \(\gcd(a,b)=1\)).

Định dạng vào:

• Một dòng gồm hai số nguyên a, b cách nhau bởi dấu cách.

Định dạng ra:

• Một số nguyên: nghiệm nguyên dương nhỏ nhất \(x_0\) thỏa mãn phương trình đồng dư.

Ví dụ, với đầu vào: 3 10 Kết quả phải in ra: 7

Ý tưởng giải

Bài toán yêu cầu tìm số \(x\) sao cho:

\[ a \cdot x \equiv 1 \pmod{b} \]

Có thể hiểu phương trình trên dưới dạng phương trình Diophantine:

\[ a \cdot x + b \cdot y = 1 \]

Với \(x, y\) là các số nguyên. Vì dữ liệu đảm bảo tồn tại nghiệm nên điều này có nghĩa là \(\gcd(a, b) = 1\).

Các bước giải:

1. Sử dụng Thuật toán Euclid mở rộng (Extended Euclid):
   Thuật toán này không chỉ tính \(\gcd(a, b)\) mà còn tìm được các số \(x\) và \(y\) thỏa mãn: \[ a \cdot x + b \cdot y = \gcd(a,b) \] Với bài toán này, ta có \(\gcd(a,b) = 1\) nên ta tìm được \(x\) là nghiệm của phương trình \(a \cdot x + b \cdot y = 1\).

2. Điều chỉnh nghiệm \(x\):
   Nghiệm \(x\) tìm được từ thuật toán có thể âm. Vì yêu cầu bài toán là nghiệm nguyên dương nhỏ nhất, ta thực hiện phép lấy modulo \(b\) trên \(x\) (tức \(x \% b\)). Nếu \(x\) âm, ta cộng thêm \(b\) cho đến khi \(x\) dương và nhỏ nhất.

Ví dụ minh họa

Giả sử đầu vào là: 3 10

• Ta cần tìm \(x\) sao cho \(3 \cdot x \equiv 1 \pmod{10}\).
• Áp dụng Extended Euclid để giải phương trình: \[ 3 \cdot x + 10 \cdot y = 1 \] Một nghiệm tìm được có thể là \(x = -3\) và \(y = 1\) (vì \(3 \cdot (-3) + 10 \cdot 1 = -9 + 10 = 1\)).
• Sau đó, ta điều chỉnh \(x\) về dạng dương: \[ x \equiv -3 \pmod{10} \Rightarrow x = (-3 \% 10 + 10) \% 10 = 7 \]
• Kiểm tra: \(3 \cdot 7 = 21\) và \(21 \mod 10 = 1\).
  Vậy, nghiệm nhỏ nhất là \(x = 7\).

Phân tích độ phức tạp

• Độ phức tạp thời gian:
  Thuật toán Euclid mở rộng có độ phức tạp \(O(\log(\min(a, b)))\), rất nhanh và hiệu quả với các giá trị \(a, b \le 2\,000\,000\,000\).

• Độ phức tạp không gian:
  Sử dụng một lượng bộ nhớ rất nhỏ, chỉ cần lưu trữ các biến kiểu số nguyên.

Như vậy, giải pháp hoạt động rất hiệu quả với các giới hạn của bài toán.

Code minh họa

Dưới đây là code C++ sử dụng thuật toán Euclid mở rộng để tìm nghiệm \(x\):

#include <iostream>
using namespace std;
typedef long long ll;

// Hàm mở rộng Euclid: Tìm x, y sao cho a*x + b*y = gcd(a,b)
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    cin >> a >> b;

    ll x, y;
    // Vì dữ liệu đảm bảo tồn tại nghiệm nên gcd(a, b) = 1.
    extended_gcd(a, b, x, y);

    // x là nghiệm của a*x + b*y = 1, nhưng có thể âm.
    // Chuyển x về dạng dương nhỏ nhất bằng cách lấy modulo b.
    x %= b;
    if(x < 0)
        x += b;

    cout << x;
    return 0;
}