Hướng dẫn giải của Ước chung, Bội chung
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
Cho N số nguyên dương (N ≤ 10, a_i ≤ 10^9). Tìm UCLN (ước chung lớn nhất) và BCNN (bội chung nhỏ nhất) của chúng. Bài toán này đơn giản nếu dùng số học chuẩn, nhưng có một thách thức ẩn: BCNN có thể rất lớn, vượt quá khả năng lưu trữ của kiểu số nguyên 64-bit (long long). Do đó, cần xử lý số lớn khi tính và in ra BCNN.
Các cách tiếp cận
Cách Chia nhỏ trung gian (Dùng cho BCNN)
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
while (b) {
long long t = a % b;
a = b;
b = t;
}
return a;
}
// Hàm nhân an toàn, kiểm tra tràn
long long safe_mul(long long a, long long b, long long limit) {
if (a == 0 || b == 0) return 0;
if (a > limit / b) return -1; // Sẽ tràn
return a * b;
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// Tính UCLN
long long ucln = a[0];
for (int i = 1; i < n; i++) {
ucln = gcd(ucln, a[i]);
}
cout << ucln << endl;
// Tính BCNN theo cách thông thường nhưng phát hiện tràn
long long bcnn = a[0];
for (int i = 1; i < n; i++) {
long long g = gcd(bcnn, a[i]);
long long t = safe_mul(bcnn / g, a[i], 1e18); // Giả sử giới hạn an toàn
if (t == -1) {
cout << "Overflow!" << endl; // Hoặc chuyển sang cách xử lý số lớn
return 0;
}
bcnn = t;
}
cout << bcnn << endl;
return 0;
}
- Time Complexity: O(N * log(max(a)))
- Space Complexity: O(1)
Cách này dùng công thức BCNN(a, b) = (a * b) / UCLN(a, b). Tuy nhiên, nếu BCNN vượt quá 64-bit, phép nhân sẽ bị tràn. Giải pháp tạm thời là kiểm tra tràn trước khi nhân. Nếu phát hiện tràn, ta phải dùng đến phương pháp số lớn (Big Integer) hoặc xử lý theo cách khác. Hàm safe_mul kiểm tra xem a * b có vượt quá giới hạn cho phép hay không trước khi thực hiện phép nhân.
Cách Phân tích thừa số nguyên tố (Prime Factorization)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Hàm phân tích thừa số nguyên tố và cập nhật số mũ lớn nhất
void updateFactors(ll num, map<ll, int>& maxExp) {
for (ll i = 2; i * i <= num; i++) {
if (num % i == 0) {
int cnt = 0;
while (num % i == 0) {
cnt++;
num /= i;
}
if (maxExp[i] < cnt) maxExp[i] = cnt;
}
}
if (num > 1) {
if (maxExp[num] < 1) maxExp[num] = 1;
}
}
// Hàm nhân số lớn (string * int)
string multiplyString(const string& num, int multiplier) {
string res = "";
int carry = 0;
for (int i = num.size() - 1; i >= 0; i--) {
int prod = (num[i] - '0') * multiplier + carry;
res.push_back(prod % 10 + '0');
carry = prod / 10;
}
while (carry) {
res.push_back(carry % 10 + '0');
carry /= 10;
}
reverse(res.begin(), res.end());
return res;
}
int main() {
int n;
cin >> n;
vector<ll> a(n);
map<ll, int> maxExp; // Lưu số mũ lớn nhất của mỗi thừa số
ll ucln_val = a[0];
// Đọc và tính UCLN
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i > 0) ucln_val = gcd(ucln_val, a[i]);
}
cout << ucln_val << endl;
// Tính BCNN: Lấy số mũ lớn nhất của từng thừa số
for (int i = 0; i < n; i++) {
updateFactors(a[i], maxExp);
}
// Tạo BCNN dưới dạng string
string bcnn_str = "1";
for (auto const& [base, exp] : maxExp) {
for (int k = 0; k < exp; k++) {
bcnn_str = multiplyString(bcnn_str, base);
}
}
cout << bcnn_str << endl;
return 0;
}
- Time Complexity: O(N * sqrt(max(a))) ~ O(10^5)
- Space Complexity: O(D) (số lượng thừa số nguyên tố)
Phương pháp này dựa trên định lý cơ bản của số học. BCNN của các số là tích của tất cả các thừa số nguyên tố chung, với số mũ là số mũ lớn nhất xuất hiện trong các số đó.
- Duyệt qua từng số a_i, phân tích ra thừa số nguyên tố.
- Dùng một map (hoặc mảng) để lưu lại số mũ lớn nhất cho mỗi số nguyên tố.
- Sau đó, nhân các thừa số nguyên tố này lại. Vì tích có thể rất lớn, ta thực hiện nhân chuỗi (string multiplication). Cách này đảm bảo tính chính xác tuyệt đối và không bị tràn số.
Cách Xử lý số lớn trực tiếp (Big Integer với String)
#include <bits/stdc++.h>
using namespace std;
// Tính UCLN bằng số học chuẩn
long long gcd(long long a, long long b) {
while (b) {
long long t = a % b;
a = b;
b = t;
}
return a;
}
// Hàm chia chuỗi thập phân cho một số nguyên (long long)
// Dùng để tính (a*b)/g khi a*b là chuỗi lớn, g là nhỏ
string divideStringByInt(const string& num, long long divisor) {
string res = "";
long long temp = 0;
for (char c : num) {
temp = temp * 10 + (c - '0');
if (temp < divisor) {
if (!res.empty()) res += '0';
} else {
res += (char)('0' + (temp / divisor));
temp %= divisor;
}
}
if (res.empty()) return "0";
return res;
}
// Hàm nhân chuỗi thập phân với số nguyên
string multiplyStringByInt(const string& num, long long multiplier) {
string res = "";
long long carry = 0;
for (int i = num.size() - 1; i >= 0; i--) {
long long prod = (long long)(num[i] - '0') * multiplier + carry;
res.push_back(prod % 10 + '0');
carry = prod / 10;
}
while (carry) {
res.push_back(carry % 10 + '0');
carry /= 10;
}
reverse(res.begin(), res.end());
return res;
}
// Hàm nhân 2 chuỗi số lớn (nếu cần thiết)
string multiplyStrings(const string& s1, const string& s2) {
if (s1 == "0" || s2 == "0") return "0";
int n = s1.length(), m = s2.length();
vector<int> res(n + m, 0);
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int mul = (s1[i] - '0') * (s2[j] - '0');
int sum = mul + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j + 2] += sum / 10;
}
}
string ans = "";
int i = 0;
while (i < res.size() && res[i] == 0) i++; // Bỏ số 0 ở đầu
for (; i < res.size(); i++) ans += (char)(res[i] + '0');
return ans;
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// Tính UCLN
long long ucln = a[0];
for (int i = 1; i < n; i++) {
ucln = gcd(ucln, a[i]);
}
cout << ucln << endl;
// Tính BCNN theo công thức: LC(a, b) = (a / GCD(a, b)) * b
// Áp dụng từng bước để tránh tràn số ngay lập tức
string bcnn = to_string(a[0]);
for (int i = 1; i < n; i++) {
long long g = gcd(a[i], stoll(bcnn)); // GCD giữa số mới và BCNN cũ (đã convert về long long được vì bcnn cũ chia hết cho GCD)
// Thực hiện: bcnn = (bcnn / g) * a[i]
// bcnn là string, g và a[i] là long long
string temp = divideStringByInt(bcnn, g); // Chia chuỗi cho số nhỏ
bcnn = multiplyStringByInt(temp, a[i]); // Nhân chuỗi mới với số nhỏ
}
cout << bcnn << endl;
return 0;
}
- Time Complexity: O(N * L) (L là độ dài chuỗi BCNN)
- Space Complexity: O(L)
Đây là cách tiếp cận thực tiễn nhất để giải quyết bài toán khi BCNN quá lớn.
- Tính UCLN bình thường.
- Tính BCNN theo công thức quen thuộc:
LC(x, y) = (x * y) / GCD(x, y). - Tuy nhiên, để tránh tràn số khi nhân
x * y, ta thực hiện từng bước:xđược lưu dưới dạng String (số lớn).yvàGCD(x, y)là số 64-bit (vìGCDluôn nhỏ hơn hoặc bằngxvày).- Bước 1: Chia chuỗi
xchoGCD. Điều này an toàn vìxchia hết choGCD. - Bước 2: Nhân kết quả (chuỗi) với
y. - Kết quả nhận được là
LCmới, vẫn dưới dạng chuỗi. Cách này kết hợp ưu điểm của số lớn và số học chuẩn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * log(max(a))) | O(1) | Chia nhỏ trung gian (Dùng cho BCNN) |
| 2 | O(N * sqrt(max(a))) ~ O(10^5) | O(D) (số lượng thừa số nguyên tố) | Phân tích thừa số nguyên tố (Prime Factorization) |
| 3 | O(N * L) (L là độ dài chuỗi BCNN) | O(L) | Xử lý số lớn trực tiếp (Big Integer với String) |
Bài học kinh nghiệm
- Công thức tính BCNN:
LC(a, b) = (a * b) / GCD(a, b). Tuy nhiên, cách tính an toàn hơn làLC(a, b) = (a / GCD(a, b)) * b. - Khi BCNN vượt quá 64-bit, cần sử dụng kỹ thuật xử lý số lớn (Big Integer). Có thể dùng Chuỗi (String) hoặc Mảng (Vector) để lưu trữ số.
- Nếu chỉ cần in ra BCNN mà không cần tính toán các phép toán phức tạp trên nó, phương pháp phân tích thừa số nguyên tố (Prime Factorization) là cách tiếp cận trực quan và đảm bảo đúng đắn.
Lỗi thường gặp
- Làm tròn số hoặc tràn số (Overflow) khi tính
a * btrước khi chia choGCD. Luôn chia trước khi nhân nếu có thể. - Quên xử lý trường hợp BCNN rất lớn, dẫn đến in ra kết quả sai (ví dụ: chỉ in phần thấp của số).
- Nếu dùng map để phân tích thừa số, cần đảm bảo cập nhật số mũ lớn nhất (
max(max_exp, current_exp)).
Bình luận