Hướng dẫn giải của Ước chung lớn nhất lớn nhất
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ìm giá trị lớn nhất của ước chung lớn nhất (GCD) của hai số phân biệt a và b trong khoảng [L, R]. Nói cách khác, cần tìm số nguyên dương m lớn nhất sao cho tồn tại hai số a, b thỏa mãn L ≤ a < b ≤ R và gcd(a, b) = m.
Các cách tiếp cận
Cách Duyệt giảm dần theo ước số (Optimized)
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
long long l, r;
cin >> l >> r;
// Duyệt m từ lớn đến nhỏ.
// Nếu tồn tại hai số bội của m trong [L, R] thì m là đáp án.
// Hai số bội của m nằm trong [L, R] có thể tìm được nếu:
// số bội lớn nhất ≤ R và số bội nhỏ nhất ≥ L.
// Số bội lớn nhất: (R / m) * m
// Số bội nhỏ nhất: ((L + m - 1) / m) * m
// Nếu số bội nhỏ nhất + m ≤ R thì tồn tại ít nhất 2 số bội.
// Hoặc tính đơn giản: số lượng bội >= 2.
// Cập nhật: Số lượng bội của m trong [L, R] là floor(R/m) - ceil(L/m) + 1.
// Điều kiện: floor(R/m) - ceil(L/m) >= 1 (tức là có ít nhất 2 số).
// ceil(L/m) = (L + m - 1) / m.
// Tuy nhiên, Solution 1 dùng vòng lặp kiểm tra số lượng bội bằng cách duyệt trực tiếp các bội.
// Solution 1:
for(int i = r; i >= 1; i--){
int cnt = 0;
// Bắt đầu từ số bội đầu tiên >= L
for(int j = ((l + i - 1) / i) * i; j >= l && j <= r; j += i){
++cnt;
}
if(cnt >= 2){ // Solution 1 ghi cnt == 2, nhưng >= 2 cũng đúng (tối ưu hơn)
cout << i;
break;
}
}
return 0;
}
- Time Complexity: O(R) trong trường hợp xấu nhất, nhưng thực tế nhanh hơn nhiều vì dừng sớm.
- Space Complexity: O(1)
Giả sử đáp án là m thì cần tồn tại ít nhất 2 số trong [L, R] là bội của m. Ta duyệt m từ R giảm dần. Với mỗi m, ta kiểm tra xem có ít nhất 2 số bội của m trong khoảng [L, R] hay không. Cách kiểm tra trong code là tính số bội đầu tiên >= L rồi đếm số bội. Vòng lặp sẽ dừng ngay khi tìm thấy m đầu tiên thỏa mãn (vì duyệt giảm dần).
Cách Duyệt theo ước số (Tối ưu hóa số học)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll l, r;
cin >> l >> r;
// Duyệt m từ r - l trở lên (hoặc từ r).
// Điều kiện: floor(r/m) - ceil(l/m) >= 1
// ceil(l/m) = (l - 1) / m (kiểu integer division)
// Điều kiện trở thành: r/m - (l-1)/m >= 2
// (r/m - (l-1)/m) chính xác là số lượng số chia hết cho m trong đoạn [l, r].
// Nếu >= 2 thì tồn tại 2 số phân biệt.
// Solution 2:
for(ll i = r - l; i >= 1; i--) {
if(r/i - (l-1)/i >= 2) {
cout << i;
return 0;
}
}
// Trường hợp không tìm thấy (rất hiếm hoặc chỉ là 1), mặc định in 1.
cout << 1;
return 0;
}
- Time Complexity: O(sqrt(R) * log R) hoặc tốt hơn, phụ thuộc vào bước nhảy. Với R-L nhỏ, vòng lặp chạy rất nhanh.
- Space Complexity: O(1)
Cách tiếp cận này dựa trên nhận định rằng nếu hai số a, b trong [L, R] chia hết cho m thì m phải là ước của (b - a). Khoảng cách lớn nhất giữa hai số phân biệt trong [L, R] là R - L. Do đó, m không thể lớn hơn R - L. Code duyệt m từ R - L giảm dần. Với mỗi m, nó kiểm tra nhanh xem có ít nhất 2 số bội của m trong đoạn [L, R] không bằng công thức số học: số lượng bội = floor(R/m) - floor((L-1)/m). Nếu >= 2 thì m là đáp án.
Cách Tối ưu hóa đoạn lặp (Loop Optimization)
#include <iostream>
using namespace std;
long long L, R;
int main(){
cin >> L >> R;
long long g = 1;
// Solution 3:
// Tối ưu vòng lặp bằng cách chỉ kiểm tra các m nằm trong đoạn [start, end]
// start ≈ (R-L+1)/2, end ≈ R-L+1
// Logic: Nếu m > R/2, số lượng bội của m trong [1, R] chỉ là 1 (chính nó).
// Để có 2 số bội trong [L, R], m không được quá lớn.
long long start = (R - L + 1) / 2;
long long end = R - L + 1;
if (end > R) end = R;
for (long long x = end; x >= start; x--){
long long cnt = R / x - (L - 1) / x;
if (cnt >= 2){
g = x;
break;
}
}
cout << g;
return 0;
}
- Time Complexity: O(R - L)
- Space Complexity: O(1)
Đây là biến thể của Approach 2, nhưng thay vì duyệt từ R-L giảm dần, nó chỉ duyệt trong một đoạn hẹp hơn được suy luận từ tính chất của phép chia. Tuy nhiên, Approach 2 đã khá tối ưu rồi. Solution 3 này thực chất có thể sai nếu R-L rất nhỏ nhưng L rất lớn (ví dụ L=10^6, R=10^6+1). Tuy nhiên, với các ràng buộc bài toán, nó hoạt động tốt. Focus chính là cách tính số lượng bội.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(R) trong trường hợp xấu nhất, nhưng thực tế nhanh hơn nhiều vì dừng sớm. | O(1) | Duyệt giảm dần theo ước số (Optimized) |
| 2 | O(sqrt(R) * log R) hoặc tốt hơn, phụ thuộc vào bước nhảy. Với R-L nhỏ, vòng lặp chạy rất nhanh. | O(1) | Duyệt theo ước số (Tối ưu hóa số học) |
| 3 | O(R - L) | O(1) | Tối ưu hóa đoạn lặp (Loop Optimization) |
Bài học kinh nghiệm
- Đáp án m phải thỏa mãn điều kiện: tồn tại ít nhất 2 số chia hết cho m trong đoạn [L, R].
- Nếu m > R - L, giữa hai số chia hết cho m trong đoạn [L, R] (nếu có) sẽ có khoảng cách ít nhất là m, vượt quá khoảng cách tối đa R-L. Do đó, ta chỉ cần kiểm tra m từ R - L trở xuống.
- Số lượng số chia hết cho m trong đoạn [L, R] được tính nhanh bằng công thức: floor(R/m) - floor((L-1)/m).
Lỗi thường gặp
- Sử dụng thuật toán tìm GCD trực tiếp cho tất cả cặp số (O((R-L)^2)) sẽ gây TLE do R-L có thể lên tới 10^7.
- Quên xử lý trường hợp L rất gần R (R-L nhỏ) có thể dẫn đến kết quả sai nếu không duyệt đủ sâu (ví dụ chỉ duyệt từ R/2).
- Lỗi tràn số nguyên khi tính toán các giá trị lớn, cần sử dụng kiểu dữ liệu long long cho L, R.
Bình luận