Hướng dẫn giải của [VTT Q4 Contest 15] Bài 1: Bội số [MINX]
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 ba số ~a, b, c~, tìm số nguyên dương ~x~ nhỏ nhất sao cho ~b \mid a x~, ~c \mid b x~, ~a \mid c x~. Mỗi điều kiện thực chất là một điều kiện "x chia hết cho một số nào đó", nên đáp án là bội chung nhỏ nhất của ba số đó.
Sub 1: Vét cạn — dùng khi ~a, b, c \le 100~
Thử lần lượt ~x = 1, 2, 3, \dots~ cho đến khi cả ba điều kiện đúng. Với ~a, b, c \le 100~ thì đáp án không quá ~10^6~ nên chạy nhanh. Nếu chỉ nộp sub này: đúng 69/100 test (31 test bị quá thời gian).
Sub 2: Công thức BCNN — ~O(T \log)~
~b \mid a x~ tương đương ~\frac{b}{\gcd(a,b)} \mid x~ (vì ~\frac{b}{\gcd(a,b)}~ và ~\frac{a}{\gcd(a,b)}~ nguyên tố cùng nhau). Tương tự ~\frac{c}{\gcd(b,c)} \mid x~ và ~\frac{a}{\gcd(c,a)} \mid x~. Vậy ~x~ nhỏ nhất là BCNN của ba số này. Tính BCNN hai lần, mỗi lần chia trước rồi nhân để tránh tràn; kết quả tối đa khoảng ~10^{18}~ nên vừa trong long long. Nếu chỉ nộp sub này: đúng 100/100 test.
Chương trình hoàn chỉnh
Hàm main đọc toàn bộ dữ liệu; nếu ~T \le 10~ và mọi số không quá 100 thì gọi sub1, ngược lại gọi sub2. 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 A[100005], B[100005], C[100005];
// Sub 1: vét cạn x = 1, 2, 3, ... đến khi thỏa cả ba điều kiện (dùng khi a, b, c <= 100)
void sub1() {
for (int i = 0; i < T; i++) {
long long a = A[i], b = B[i], c = C[i];
long long x = 1;
while (!((a * x) % b == 0 && (b * x) % c == 0 && (c * x) % a == 0)) x++;
cout << x << "\n";
}
}
// Sub 2: a*x chia hết cho b <=> x chia hết cho b/gcd(a,b). Tương tự cho hai điều kiện còn lại.
// Đáp án = BCNN của ba số b/gcd(a,b), c/gcd(b,c), a/gcd(c,a).
void sub2() {
for (int i = 0; i < T; i++) {
long long a = A[i], b = B[i], c = C[i];
long long p = b / __gcd(a, b);
long long q = c / __gcd(b, c);
long long r = a / __gcd(c, a);
long long l = p / __gcd(p, q) * q; // l <= 10^12
l = l / __gcd(l, r) * r; // kết quả <= 10^18
cout << l << "\n";
}
}
int main() {
freopen("MINX.INP", "r", stdin);
freopen("MINX.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 >> A[i] >> B[i] >> C[i];
mx = max(mx, max(A[i], max(B[i], C[i])));
}
if (T <= 10 && mx <= 100) sub1();
else sub2();
}
Bình luận