Hướng dẫn giải của Làm tròn số 2
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.
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
, , ,
Hiểu bài toán
Bài toán yêu cầu tính toán phép chia lấy phần nguyên của hai số nguyên dương rất lớn a và b, với a, b có thể lên tới 10^100000. Nói cách khác, cần tìm giá trị floor(a / b). Do kích thước của số quá lớn để lưu trữ trong các kiểu dữ liệu nguyên tố cơ bản (như long long), chúng ta cần xử lý số học trên các số lớn (Big Integer) hoặc sử dụng các kỹ thuật đặc biệt để chia số lớn cho số lớn.
Các cách tiếp cận
Cách Thư viện Big Integer
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
// Cấu trúc lưu số lớn (Big Integer)
struct BigInt {
string value;
BigInt(string s = "0") {
if (s.empty()) value = "0";
else value = s;
}
// Phép chia BigInt cho BigInt, trả về phần nguyên
string divideBy(const BigInt& divisor) const {
if (divisor.value == "0") return "Error";
if (*this < divisor) return "0";
string quotient = "";
string remainder = "";
for (char digit : value) {
remainder += digit;
// Bỏ qua các số 0 ở đầu
remainder.erase(0, min(remainder.find_first_not_of('0'), remainder.size() - 1));
int count = 0;
while (remainder != "0" && !isLessThan(remainder, divisor.value)) {
remainder = subtract(remainder, divisor.value);
count++;
}
quotient += to_string(count);
}
// Bỏ qua số 0 ở đầu
quotient.erase(0, min(quotient.find_first_not_of('0'), quotient.size() - 1));
if (quotient.empty()) quotient = "0";
return quotient;
}
// So sánh hai chuỗi số số
bool isLessThan(const string& a, const string& b) const {
if (a.length() != b.length()) return a.length() < b.length();
return a < b;
}
bool operator<(const BigInt& other) const {
return isLessThan(this->value, other.value);
}
// Trừ hai chuỗi số (a - b), giả định a >= b
static string subtract(string a, string b) {
int n = a.length(), m = b.length();
string res = "";
int i = n - 1, j = m - 1, borrow = 0;
while (i >= 0 || j >= 0) {
int digitA = (i >= 0) ? a[i] - '0' : 0;
int digitB = (j >= 0) ? b[j] - '0' : 0;
int sub = digitA - digitB - borrow;
if (sub < 0) {
sub += 10;
borrow = 1;
} else {
borrow = 0;
}
res.push_back(sub + '0');
i--; j--;
}
while (res.size() > 1 && res.back() == '0') res.pop_back();
reverse(res.begin(), res.end());
return res;
}
};
int main() {
string a, b;
cin >> a >> b;
BigInt A(a), B(b);
cout << A.divideBy(B) << endl;
return 0;
}
- Time Complexity: O(N * M) (N, M là số chữ số của a, b)
- Space Complexity: O(N + M)
Đây là cách tiếp cận mô phỏng lại phép chia như cách chúng ta làm bằng tay. Chúng ta lần lượt lấy từng chữ số của số bị chia (a), ghép vào số dư hiện tại, rồi trừ đi số chia (b) nhiều lần cho đến khi số dư nhỏ hơn b. Số lần trừ được ghi nhận vào kết quả. Cách này chậm vì với mỗi chữ số của kết quả, có thể phải thực hiện nhiều phép trừ. Tuy nhiên, nó dễ hiểu và phù hợp với dữ liệu nhỏ hơn (vẫn chạy được cho 10^100000 nhưng chậm).
Cách Chia lấy dư trực tiếp (Simulation)
#include <bits/stdc++.h>
using namespace std;
const int base = 1000000000;
struct BigInt {
vector<int> a;
int sign;
BigInt() : sign(1) {}
BigInt(long long v) { *this = v; }
BigInt(const string &s) { read(s); }
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
if (s[0] == '-') {
sign = -1;
pos = 1;
}
for (int i = s.length() - 1; i >= pos; i -= 9) {
int x = 0;
for (int j = max(pos, i - 8); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
void trim() {
while (!a.empty() && a.back() == 0) a.pop_back();
if (a.empty()) sign = 1;
}
bool operator<(const BigInt &v) const {
if (sign != v.sign) return sign < v.sign;
if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign;
return false;
}
BigInt operator-(const BigInt &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
BigInt res = *this;
for (int i = 0, borrow = 0; i < (int)v.a.size() || borrow; ++i) {
res.a[i] -= borrow + (i < (int)v.a.size() ? v.a[i] : 0);
if (res.a[i] < 0) {
res.a[i] += base;
borrow = 1;
} else borrow = 0;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
BigInt operator-() const {
BigInt res = *this;
res.sign = -sign;
return res;
}
BigInt abs() const {
BigInt res = *this;
res.sign = 1;
return res;
}
// Phép chia BigInt cho BigInt
pair<BigInt, BigInt> div_mod(const BigInt &v) const {
if (v.a.empty()) return {BigInt(), BigInt()};
BigInt q, r;
q.a.resize(a.size());
for (int i = a.size() - 1; i >= 0; i--) {
r.a.insert(r.a.begin(), a[i]);
r.trim();
// Ước lượng số lần chia
long long guess = 0;
if (r.a.size() > v.a.size()) {
long long high = (long long)r.a.back() * base + r.a[r.a.size() - 2];
long long low = v.a.back();
guess = min(base - 1, high / low);
} else if (r.a.size() == v.a.size()) {
guess = ((long long)r.a.back() * base + r.a[r.a.size() - 2]) / v.a.back();
}
BigInt tempV = v;
BigInt tempRes = BigInt((long long)guess);
while ((tempV * tempRes) <= r) {
guess++;
tempRes = BigInt((long long)guess);
}
guess--;
tempRes = BigInt((long long)guess);
q.a[i] = guess;
r = r - (v * tempRes);
}
q.trim();
r.trim();
q.sign = sign * v.sign;
r.sign = sign;
if (q.sign == 0) q.sign = 1;
if (r.sign == 0) r.sign = 1;
return {q, r};
}
BigInt operator*(const BigInt &v) const {
BigInt res;
res.sign = sign * v.sign;
res.a.resize(a.size() + v.a.size());
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] == 0) continue;
long long carry = 0;
for (int j = 0; j < (int)v.a.size() || carry; j++) {
long long cur = res.a[i + j] + 1LL * a[i] * (j < (int)v.a.size() ? v.a[j] : 0) + carry;
res.a[i + j] = cur % base;
carry = cur / base;
}
}
res.trim();
return res;
}
void print() {
if (a.empty()) { cout << 0; return; }
if (sign == -1) cout << '-';
cout << a.back();
for (int i = a.size() - 2; i >= 0; i--)
cout << setfill('0') << setw(9) << a[i];
}
};
int main() {
string s1, s2;
cin >> s1 >> s2;
BigInt A(s1), B(s2);
pair<BigInt, BigInt> res = A.div_mod(B);
res.first.print();
return 0;
}
- Time Complexity: O(N^2 / M) hoặc O(N * M)
- Space Complexity: O(N / 9)
Đây là giải pháp tối ưu từ các submission được cung cấp. Nó sử dụng cơ sở số 10^9 (mỗi phần tử vector lưu 9 chữ số) để giảm kích thước vector và số lần lặp. Phép chia được thực hiện theo thuật toán chia dài tương tự như trong bài toán chia số lớn cơ bản.
- Tách số thành các khối (base 10^9).
- Duyệt từ chữ số cao nhất của a.
- Với mỗi bước, thêm chữ số của a vào số dư.
- Dùng ước lượng (estimation) dựa trên 2 chữ số đầu của số dư và 1 chữ số đầu của số chia để tìm số lần trừ (giả).
- Kiểm tra lại và điều chỉnh.
- Trừ số chia * số ước lượng ra khỏi số dư.
Đây là phương pháp hiệu quả nhất cho các số lớn.
Cách Xử lý chuỗi ký tự (String Processing)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// So sánh 2 chuỗi số
bool smallerOrEqual(string a, string b) {
if (a.length() < b.length()) return true;
if (a.length() > b.length()) return false;
return a <= b;
}
// Trừ 2 chuỗi số
string subtract(string a, string b) {
int n = a.length(), m = b.length();
string res = "";
int i = n - 1, j = m - 1, borrow = 0;
while (i >= 0) {
int digitA = a[i] - '0' - borrow;
int digitB = (j >= 0) ? b[j] - '0' : 0;
if (digitA < digitB) {
digitA += 10;
borrow = 1;
} else {
borrow = 0;
}
res.push_back((digitA - digitB) + '0');
i--; j--;
}
while (res.length() > 1 && res.back() == '0') res.pop_back();
reverse(res.begin(), res.end());
return res;
}
string divide(string a, string b) {
if (smallerOrEqual(a, b) == false && b == "0") return "0";
if (b == "0") return "0";
if (smallerOrEqual(a, b)) {
if (a == b) return "1";
if (a < b) return "0";
}
string quotient = "";
string curr = "";
for (int i = 0; i < a.length(); i++) {
curr += a[i];
// Bỏ qua số 0 ở đầu
size_t firstNotZero = curr.find_first_not_of('0');
if (firstNotZero == string::npos) curr = "0";
else if (firstNotZero > 0) curr = curr.substr(firstNotZero);
int count = 0;
while (smallerOrEqual(b, curr)) {
curr = subtract(curr, b);
count++;
}
quotient += (count + '0');
}
// Bỏ qua số 0 ở đầu
size_t firstNotZero = quotient.find_first_not_of('0');
if (firstNotZero == string::npos) return "0";
return quotient.substr(firstNotZero);
}
int main() {
string a, b;
cin >> a >> b;
cout << divide(a, b) << endl;
return 0;
}
- Time Complexity: O(Len(a) * Len(b) * 9)
- Space Complexity: O(Len(a) + Len(b))
Cách này sử dụng chuỗi string để lưu trữ số. Nó mô phỏng phép chia bằng cách lần lượt lấy các ký tự của a, đưa vào biến 'curr' (số dư tạm thời). Sau đó, trừ b khỏi curr nhiều lần cho đến khi curr < b. Số lần trừ được ghi vào kết quả. Tuy nhiên, thay vì trừ từng đơn vị, ta có thể trừ nhiều hơn (ví dụ trừ b * 10, b * 5...) để tăng tốc độ, nhưng đoạn code mẫu này thực hiện trừ từng đơn vị. Đây là cách tiếp cận cơ bản nhất, hiệu quả với dữ liệu vừa phải.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M) (N, M là số chữ số của a, b) | O(N + M) | Thư viện Big Integer |
| 2 | O(N^2 / M) hoặc O(N * M) | O(N / 9) | Chia lấy dư trực tiếp (Simulation) |
| 3 | O(Len(a) * Len(b) * 9) | O(Len(a) + Len(b)) | Xử lý chuỗi ký tự (String Processing) |
Bài học kinh nghiệm
- Vì số a, b quá lớn (đến 10^100000), không thể dùng các kiểu dữ liệu cơ bản của C++ (long long) hay Java (BigInteger mặc dù Java có, nhưng để hiểu thuật toán thì cần mô phỏng). Phải dùng mảng/vector hoặc chuỗi.
- Thuật toán chia dài hiệu quả nhất thường chia thành các khối nhỏ hơn (ví dụ base 10^9 trong C++) để giảm số lần lặp và tối ưu hóa phép nhân/phép trừ.
- Việc ước lượng số lần chia (guess) trong mỗi bước là then chốt để giảm độ phức tạp từ O(N^2) xuống O(N * M) hoặc tốt hơn. Thay vì trừ b 1 lần mỗi bước, ta ước lượng xem có thể trừ b bao nhiêu lần (ví dụ 50 lần) rồi trừ luôn 50*b.
Lỗi thường gặp
- Xử lý số 0 ở đầu của kết quả (ví dụ 00123 -> 123).
- Xử lý số dư khi số chia lớn hơn số bị chia ban đầu.
- Lỗi tràn số khi thực hiện các phép tính toán trung gian (ví dụ khi ước lượng trong base 10^9, cần dùng kiểu long long để chứa kết quả nhân trung gian).
- Hiệu năng: Việc trừ lặp lại nhiều lần (trừ 1 lần mỗi bước) cho các số lớn sẽ rất chậm, dẫn đến TLE (Time Limit Exceeded). Cần tối ưu bằng cách dùng ước lượng hoặc thuật toán chia dài chuẩn.
Bình luận