Hướng dẫn giải của Thương và dư


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, lhm, rukiku824, The_Black_Silence

Hiểu bài toán

Cho hai số nguyên dương lớn $n$ và $k$ (đến $10^{100}$), bài toán yêu cầu tìm hai số nguyên $p$ (thương) và $r$ (dư) sao cho $n = p \times k + r$ và $0 \le r < k$. Đây là phép chia có dư trên các số lớn (Big Integer Division). Do $n$ và $k$ quá lớn để lưu trữ trong các kiểu dữ liệu nguyên cơ bản, ta cần xử lý chúng dưới dạng chuỗi ký tự.

Các cách tiếp cận

Cách Phép chia dài (Long Division)
#include <bits/stdc++.h>
using namespace std;

// So sánh hai số lớn dạng chuỗi
int cmp(string a, string b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    if (a == b) return 0;
    return a < b ? -1 : 1;
}

// Trừ một số lớn b khỏi a (a >= b)
string sub(string a, string b) {
    int carry = 0;
    for (int i = 0; i < (int)b.size() || carry; i++) {
        int ai = a[a.size()-1-i] - '0';
        int bi = (i < (int)b.size() ? b[b.size()-1-i]-'0' : 0);
        int d = ai - bi - carry;
        carry = d < 0;
        if (carry) d += 10;
        a[a.size()-1-i] = d + '0';
    }
    while (a.size() > 1 && a[0] == '0') a.erase(a.begin());
    return a;
}

void bigDivide(string n, string k, string &q, string &r) {
    q = "";
    r = "";
    for (char c : n) {
        if (r == "0") r = "";
        r.push_back(c);
        while (cmp(r, k) >= 0) {
            r = sub(r, k);
            if (q == "") q = "0";
            // Tăng thương (đơn giản là + 1 vào chuỗi q)
            // Trong thực tế cần thêm hàm cộng chuỗi cho q, giả định q tăng từng đơn vị
             int idx = q.size() - 1;
             while (idx >= 0 && q[idx] == '9') {
                 q[idx] = '0';
                 idx--;
             }
             if (idx < 0) q.insert(q.begin(), '1');
             else q[idx]++;
        }
    }
    if (q == "") q = "0";
    if (r == "") r = "0";
}

int main() {
    string n, k;
    cin >> n >> k;
    string p, r;
    bigDivide(n, k, p, r);
    cout << p << " " << r << endl;
    return 0;
}
  • Time Complexity: O(L^2) hoặc O(L * k), với L là độ dài chuỗi n.
  • Space Complexity: O(L)

Phương pháp này mô phỏng chính xác cách chia dài từng cột mà chúng ta học ở trường. Với mỗi chữ số trong $n$, ta đưa nó vào phần dư hiện tại. Nếu phần dư lớn hơn hoặc bằng $k$, ta trừ $k$ đi một lần, tăng thương lên 1 và lặp lại cho đến khi phần dư nhỏ hơn $k$. Các hàm cmpsub là cần thiết để so sánh và trừ các số lớn dạng chuỗi. Phương pháp này trực quan nhưng có thể chậm nếu $k$ rất nhỏ so với $n$ (ví dụ $n$ có 100 chữ số, $k=2$, thì với mỗi chữ số của $n$ ta có thể phải lặp jusquử 9 lần). Tuy nhiên, với các số lớn ngẫu nhiên, hiệu năng thường chấp nhận được.

Cách Phép chia dài tối ưu (Tính thương trực tiếp)
#include <bits/stdc++.h>
using namespace std;

string div(string n, string k, string &r) {
    if (k == "0") return "";
    if (cmp(n, k) < 0) {
        r = n;
        return "0";
    }

    string q = "";
    r = "";
    for (int i = 0; i < n.size(); i++) {
        r += n[i];
        r.erase(0, min(r.find_first_not_of('0'), r.size()-1)); // Remove leading zeros

        // Estimate quotient digit
        // Note: This is a simplified estimation. A robust solution might need
        // to handle the case where the estimated digit is too high.
        if (cmp(r, k) < 0) {
            if (q != "") q += "0";
            continue;
        }

        int digit = 0;
        // Tính toán digit bằng cách trừ dần
        // Hoặc dùng phép chia cận biên (binary search) cho digit
        // Code dưới đây là cách trừ từng đơn vị cho đến khi r < k
        string temp = r;
        while (cmp(temp, k) >= 0) {
            temp = sub(temp, k);
            digit++;
        }
        r = temp;
        q += (char)(digit + '0');
    }
    if (q == "") q = "0";
    if (r == "") r = "0";
    return q;
}

// Cần hàm cmp và sub như approach 1
int cmp(string a, string b) { ... } 
string sub(string a, string b) { ... }

int main() {
    string n, k, r;
    cin >> n >> k;
    cout << div(n, k, r) << " " << r << endl;
}
  • Time Complexity: O(L * k) đến O(L^2)
  • Space Complexity: O(L)

Đây là cách tối ưu hóa của Approach 1. Thay vì chỉ đơn thuần mô phỏng từng cột, ta có thể tối ưu việc tính toán thương cho mỗi cột. Trong code mẫu, ta vẫn sử dụng vòng lặp trừ để tìm thương của mỗi cột, nhưng cấu trúc code rõ ràng hơn. Một tối ưu quan trọng khác (được đề cập trong các giải pháp đã cho) là sử dụng ước lượng (estimation) để tìm thương của mỗi cột thay vì trừ từng lần một. Ví dụ, lấy $\lceil \frac{10 \cdot \text{phần dư}i + \text{chữ số}{i+1}}{k} \rceil$. Tuy nhiên, việc này đòi hỏi hàm nhân chuỗi và chia cận biên. Code mẫu ở trên giữ logic trừ lặp lại để dễ hiểu, nhưng về cơ bản vẫn là cách chia dài.

Cách Sử dụng thư viện (Nếu ngôn ngữ hỗ trợ)
// Ví dụ sử dụng boost::multiprecision hoặc tự implement BigInt class
// Do C++ chuẩn không hỗ trợ BigInt, đây là pseudocode cho cách tiếp cận hướng đối tượng

class BigInt {
    string num;
public:
    BigInt(string s) : num(s) {}
    // ... các phép toán -, / ...
};

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    BigInt n(s1), k(s2);
    BigInt p = n / k;
    BigInt r = n % k;
    cout << p.toString() << " " << r.toString();
}
  • Time Complexity: Thường là O(N log N) hoặc tốt hơn tùy thư viện
  • Space Complexity: O(N)

Trong các kỳ thi lập trình cạnh tranh, C++ thường không có sẵn BigInt trong std. Tuy nhiên, các giải pháp đã cho cho thấy cách tự implement. Nếu dùng Java (BigInteger) hoặc Python, bài toán này chỉ mất 1 dòng code. Approach này chủ yếu để chỉ ra rằng bản chất vấn đề là Big Integer Arithmetic.

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

Cách tiếp cận Time Space Tên
1 O(L^2) hoặc O(L * k), với L là độ dài chuỗi n. O(L) Phép chia dài (Long Division)
2 O(L * k) đến O(L^2) O(L) Phép chia dài tối ưu (Tính thương trực tiếp)
3 Thường là O(N log N) hoặc tốt hơn tùy thư viện O(N) Sử dụng thư viện (Nếu ngôn ngữ hỗ trợ)

Bài học kinh nghiệm

  • Bài toán là phép chia có dư cơ bản nhưng với số liệu kích thước lớn (Big Integer). Thay vì dùng số nguyên, ta dùng chuỗi ký tự.
  • Vòng lặp while (n >= k) n -= k là logic cốt lõi, nhưng cần được tối ưu hóa cho chuỗi (trừ chuỗi) và tốc độ.
  • Cần xử lý ký tự '0' ở đầu chuỗi kết quả (ví dụ: 05 -> 5).

Lỗi thường gặp

  • Làm sai phép toán trừ chuỗi khi có số âm ở các cột (quên xử lý borrow/carry).
  • Xử lý sai các số 0 ở đầu đầu vào hoặc đầu ra (ví dụ 000123).
  • Vòng lặp vô hạn nếu phép trừ không đúng hoặc điều kiện dừng sai.
  • Tính toán sai số digit thương dẫn đến kết quả sai.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.