Hướng dẫn giải của [VTT Q4 Contest 14] Bài 2: Ước chung lớn nhất [BOBASO]
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
Cần tìm ba số khác nhau ~a, b, c~ có tổng ~n~, ~\gcd(a, b) = c~ và tích ~abc~ lớn nhất. Điều kiện ~\gcd(a,b)=c~ cho phép viết ~a = cx~, ~b = cy~ với ~\gcd(x, y) = 1~, từ đó bài toán quy về duyệt ước của ~n~.
Sub 1: Vét cạn — ~O(n^2)~ mỗi truy vấn, dùng khi ~t \le 10~ và ~n \le 5000~
Duyệt mọi cặp ~a < b~, đặt ~c = n - a - b~, kiểm tra ~c~ dương, ba số đôi một khác nhau và ~\gcd(a, b) = c~, rồi giữ bộ có tích lớn nhất. Nếu chỉ nộp sub này: đúng 6/11 test (5 test lớn bị quá giờ).
Sub 2: Duyệt ước và chọn ~x, y~ gần nhau — ~O(\text{số ước} \cdot \text{ít bước})~ mỗi truy vấn
Từ ~a + b + c = n~ ta có ~c(x + y + 1) = n~, nên ~c~ là ước của ~n~ và ~x + y = m = n/c - 1~. Vì ~\gcd(x, y) = 1~ nên ~\gcd(x, m) = 1~. Ba số khác nhau tương đương ~x \ne y~, ~x \ge 2~, ~y \ge 2~ (tức ~x, y \ne 1~, nếu không ~a = c~ hoặc ~b = c~).
Với mỗi ước ~c~, tích ~c^3 xy~ lớn nhất khi ~xy~ lớn nhất, tức ~x~ gần ~m/2~ nhất. Ta cho ~x~ chạy từ ~\lfloor (m-1)/2 \rfloor~ giảm dần đến khi ~\gcd(x, m) = 1~; thường dừng rất sớm. Sàng ước nguyên tố nhỏ nhất đến ~10^6~ để phân tích ~n~ và sinh các ước nhanh, sau đó lấy bộ tốt nhất trên mọi ước ~c~. Nếu chỉ nộp sub này: đúng 11/11 test.
Chương trình hoàn chỉnh
Chương trình đọc các truy vấn; nếu ~t \le 10~ và ~n \le 5000~ 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. Chấm thử: chương trình đầy đủ đúng 11/11 test.
#include <bits/stdc++.h>
using namespace std;
int t;
int q[100005];
int spf[1000005];
// Sub 1: vét cạn a < b, c = n - a - b — ~O(n^2)~ mỗi truy vấn, dùng khi n <= 5000
void sub1() {
for (int k = 0; k < t; k++) {
int n = q[k];
long long best = -1;
int ra = 0, rb = 0, rc = 0;
for (int a = 1; a <= n; a++)
for (int b = a + 1; a + b < n; b++) {
int c = n - a - b;
if (c == a || c == b) continue;
if (a % c || b % c) continue;
if (__gcd(a, b) != c) continue;
long long p = 1LL * a * b * c;
if (p > best) { best = p; ra = a; rb = b; rc = c; }
}
printf("%d %d %d\n", ra, rb, rc);
}
}
// Sub 2: a = c*x, b = c*y, gcd(x,y)=1, x+y = n/c - 1, x,y >= 2, x != y.
// Duyệt ước c của n; với mỗi c lấy x gần m/2 nhất (x < y) sao cho gcd(x, m) = 1.
void sub2() {
for (int i = 2; i <= 1000000; i++)
if (!spf[i])
for (int j = i; j <= 1000000; j += i)
if (!spf[j]) spf[j] = i;
for (int k = 0; k < t; k++) {
int n = q[k];
// sinh các ước của n từ phân tích ra thừa số nguyên tố
vector<int> d = {1};
for (int x = n; x > 1;) {
int p = spf[x], e = 0;
while (x % p == 0) { x /= p; e++; }
int sz = d.size(), pw = 1;
for (int i = 0; i < e; i++) {
pw *= p;
for (int j = 0; j < sz; j++) d.push_back(d[j] * pw);
}
}
sort(d.begin(), d.end());
long long best = -1;
int ra = 0, rb = 0, rc = 0;
for (int c : d) {
int m = n / c - 1;
if (m < 5) continue;
for (int x = (m - 1) / 2; x >= 2; x--) { // x < m - x
if (__gcd(x, m) == 1) {
long long p = 1LL * c * c * c * x * (m - x);
if (p > best) { best = p; ra = c * x; rb = c * (m - x); rc = c; }
break;
}
}
}
printf("%d %d %d\n", ra, rb, rc);
}
}
int main() {
freopen("BOBASO.INP", "r", stdin);
freopen("BOBASO.OUT", "w", stdout);
scanf("%d", &t);
int mx = 0;
for (int i = 0; i < t; i++) { scanf("%d", &q[i]); mx = max(mx, q[i]); }
if (t <= 10 && mx <= 5000) sub1();
else sub2();
}
Bình luận