Hướng dẫn giải của [VTT Q4 Contest 11] Bài 1: Bội chung nhỏ nhất [LCM]
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.
Hướng dẫn giải
Cho đoạn ~[l, r]~, cần tìm hai số ~x < y~ trong đoạn sao cho ~LCM(x, y)~ cũng nằm trong đoạn. Nhận xét then chốt: ~LCM(x, y) \ge y > x \ge l~, nên chỉ cần lo ~LCM(x, y) \le r~.
Sub 1: Vét cạn — dùng khi ~r \le 100~
Thử lần lượt ~x~ từ ~l~ tăng dần; với mỗi ~x~ thử các bội ~y = 2x, 3x, \dots~ không vượt quá ~r~ (khi ~y~ là bội của ~x~ thì ~LCM(x, y) = y~). Gặp cặp đầu tiên thì in ra, không có thì in ~-1~ ~-1~. Nếu chỉ nộp sub này: đúng 14/20 test (các test lớn bị quá thời gian).
Sub 2: Duyệt ~x~ — dùng khi ~t = 1, r \le 10^7~
Cặp ~(x, 2x)~ có ~LCM = 2x~, nên ~x~ dùng được khi ~2x \le r~. Duyệt ~x~ từ ~l~ đến ~r~ và dừng ở ~x~ đầu tiên thỏa ~2x \le r~: mất ~O(r)~ cho một truy vấn. Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 3: Công thức ~O(1)~ mỗi truy vấn
Nếu ~2l \le r~ thì ~(l, 2l)~ là đáp án. Ngược lại, mọi ~x \ge l~ và ~y > x~ đều có ~y \ge x + 1~; nếu ~y~ là bội của ~x~ thì ~y \ge 2x \ge 2l > r~, còn nếu không thì ~LCM(x, y) \ge 2y > 2x \ge 2l > r~ (vì ~LCM~ là bội thật sự của ~y~). Vậy không tồn tại đáp án. Đáp án đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc toàn bộ truy vấn; nếu mọi ~r \le 100~ thì gọi sub1, nếu ~t = 1~ và ~r \le 10^7~ thì gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int t;
long long L[100005], R[100005];
// Sub 1: vét cạn — r <= 100. Thử x tăng dần, y là bội của x (khi đó LCM(x,y) = y).
void sub1() {
for (int i = 0; i < t; i++) {
long long l = L[i], r = R[i];
long long X = -1, Y = -1;
for (long long x = l; x <= r && X < 0; x++)
for (long long y = 2 * x; y <= r; y += x) {
X = x; Y = y; break;
}
cout << X << " " << Y << "\n";
}
}
// Sub 2: r <= 1e7 — duyệt x từ l, dừng ngay khi 2x <= r (mỗi truy vấn ~O(r))
void sub2() {
for (int i = 0; i < t; i++) {
long long l = L[i], r = R[i], X = -1, Y = -1;
for (long long x = l; x <= r; x++)
if (2 * x <= r) { X = x; Y = 2 * x; break; }
cout << X << " " << Y << "\n";
}
}
// Sub 3: đầy đủ — có đáp án khi và chỉ khi 2l <= r, khi đó (l, 2l)
void sub3() {
for (int i = 0; i < t; i++) {
if (2 * L[i] <= R[i]) cout << L[i] << " " << 2 * L[i] << "\n";
else cout << "-1 -1\n";
}
}
int main() {
freopen("LCM.INP", "r", stdin);
freopen("LCM.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> t;
long long mx = 0;
for (int i = 0; i < t; i++) { cin >> L[i] >> R[i]; mx = max(mx, R[i]); }
if (mx <= 100) sub1();
else if (t == 1 && mx <= 10000000) sub2();
else sub3();
}
Bình luận