BFS trên phần dư (BFS Remainder)🕵️

🔗 Bài toán kinh điển: ONEZERO - Ones and zeros

I. Tóm tắt đề bài

Cho một số nguyên dương $n$. Hãy tìm số nguyên dương $X$ nhỏ nhất thỏa mãn đồng thời hai điều kiện:

• $X$ là bội số của $n$ (nghĩa là $X$ chia hết cho $n$).
• Trong hệ thập phân, $X$ chỉ gồm các chữ số 0 và 1 (và phải bắt đầu bằng chữ số 1).

Input:

• Dòng đầu tiên là số lượng bộ test $K$ ($K \approx 1000$).
• $K$ dòng tiếp theo, mỗi dòng chứa một số nguyên $n$ ($1 \le n \le 20000$).

Output:

• Với mỗi số $n$, in ra trên một dòng số $X$ nhỏ nhất tương ứng tìm được.

Ví dụ:

• Nếu $n = 3$, số nhỏ nhất gồm 0 và 1 chia hết cho 3 là 111.
• Nếu $n = 7$, số nhỏ nhất là 1001.
• Nếu $n = 17$, số nhỏ nhất là 11101.

II. Tại sao lại dùng BFS?

Bài toán yêu cầu tìm số nhỏ nhất thỏa mãn điều kiện.

Thuật toán BFS duyệt các trạng thái theo từng “lớp” (từ ngắn đến dài). Do đó, khi ta sinh ra các số chỉ gồm 0 và 1 theo thứ tự: $\quad 1 \rightarrow \quad 10, 11 \quad \rightarrow \quad 100, 101, 110, 111 \quad \rightarrow \quad$ …

Số đầu tiên trong quá trình sinh này chia hết cho $n$ chắc chắn sẽ là số có giá trị nhỏ nhất.

III. Vấn đề

Các số sinh ra chỉ gồm ‘0’ và ‘1’ có thể dài đến hàng trăm chữ số, vượt qua giới hạn của mọi kiểu dữ liệu số nguyên thông thường nên ta bắt buộc phải dùng string.

Tuy nhiên, nếu chỉ đơn thuần sinh ra các string chỉ chứa kí tự $1, 0$ (sử dụng Queue hoặc quay lui) thì độ phức tạp có thể lên đến $O(2^k)$ với k là độ dài xâu. Với $n = 20000$, số chữ số có thể lên tới hàng chục, hàng trăm, khiến $2^{100}$ là một con số không thể tính toán nổi.

IV. Tính chất của đồng dư thức

Toán học đồng dư có một tính chất cực kỳ lợi hại:

• Giả sử ta có một số $X$, và ta biết số dư của $X$ khi chia cho $n$ là $r$.
• Khi ta thêm chữ số $d$ vào sau số $X$, số mới tạo thành sẽ là $X \cdot 10 + d$.
• Số dư của số mới này khi chia cho $n$ hoàn toàn có thể được tính dựa trên $r$:

\[X \cdot 10 + d \equiv r \cdot 10 + d \pmod n\]

V. Tối ưu sử dụng mảng đánh dấu (pruning)

• Vì ta chia lấy dư cho $n$, nên chỉ có tối đa $n$ trạng thái số dư (từ 0 đến $n-1$).
• Giả sử trong quá trình BFS, ta tạo ra hai chuỗi “101” và “1100” và chúng có cùng một số dư $r$ khi chia cho $n$. Ta chỉ cần giữ lại chuỗi sinh ra trước (chuỗi ngắn hơn), và bỏ qua chuỗi sinh sau. Vì nếu cả hai cùng đi tiếp một chặng đường giống hệt nhau để đến số dư 0, thì chuỗi ngắn hơn chắc chắn sẽ tạo ra kết quả nhỏ hơn.
• Bằng việc sử dụng visited[$r$], ta giới hạn số lượng trạng thái trong Queue tối đa là $n$.

$\Rightarrow$ Độ phức tạp thời gian giảm xuống chỉ còn $O(n)$ thay vì $O(2^k)$.

VI. Mã giải

const int limN = 20000 + 5;
int visited[limN];
int trace[limN];
int digit[limN];
int session = 0; // trick tối ưu bộ nhớ thay vì cứ phải memset mỗi testcase
void solve() {
    session++;
    int n; cin >> n;
    queue<int> qu;
    int start_r = 1 % n;
    if(start_r == 0) return cout << 1 << nl, void();
    visited[start_r] = session;
    trace[start_r] = -1; // ko có cha
    digit[start_r] = 1;
    qu.push(start_r);
    while(!qu.empty()) {
        int r = qu.front(); qu.pop();
        if(r == 0) break; // tìm thấy số nhỏ nhất chia hết cho n
        for(const int &k: {0, 1}) {
            int nr = (r * 10 + k) % n;
            if(visited[nr] != session) {
                visited[nr] = session;
                trace[nr] = r;
                digit[nr] = k;
                qu.push(nr);
            }
        }
    }
    int last = 0;
    string res;
    while(last != -1) {
        res.pb(char('0' + digit[last]));
        last = trace[last];
    }
    reverse(all(res));
    cout << res << nl;
}