Hướng dẫn giải của [VTT Q4 Contest 02] Bài 2: Tháp đầy đủ [TOWER]
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
Tháp đầy đủ của ~(a, b)~ là dãy ước số mà mỗi bước nhân với một số nguyên tố (nếu nhân với hợp số thì chèn được đĩa vào giữa). Vì vậy cần ~a \mid b~, và tháp ứng với một cách sắp xếp các thừa số nguyên tố của ~b/a~.
Sub 1: Vét cạn — dùng khi ~b/a \le 10^4~
Từ đĩa ~x~ (bắt đầu ~x = a~), thử nhân với từng số nguyên tố ~p~ là ước của ~b/x~, đệ quy cho đến khi ~x = b~, lấy tổng nhỏ nhất. Nếu ~a~ không là ước của ~b~ thì in -1. Nếu chỉ nộp sub này: đúng 18/20 test (2 test lớn quá giờ).
Sub 2: Sắp xếp thừa số nguyên tố — ~O(\sqrt{b/a})~
Chiều cao luôn bằng số thừa số nguyên tố (tính cả bội) của ~b/a~ cộng 1. Tổng ~a + a p_1 + a p_1 p_2 + \dots~ nhỏ nhất khi các thừa số nhỏ được nhân trước, nên nhân các số nguyên tố theo thứ tự tăng dần. Phân tích ~b/a~ bằng chia thử đến ~\sqrt{r}~ (tối đa ~10^6~), phần dư lớn hơn 1 là một số nguyên tố. Trường hợp ~a = b~ cho kết quả 1 a. Tổng có thể lớn nên dùng long long. Chương trình đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~a, b~; nếu ~b/a~ nhỏ 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;
long long a, b;
// Sub 1: vét cạn — thử mọi cách chọn bước nhân một số nguyên tố, dùng khi b/a nhỏ
long long best;
int bestH;
void dfs(long long x, long long sum, int h) {
if (x == b) {
if (sum < best) { best = sum; bestH = h; }
return;
}
long long r = b / x;
for (long long p = 2; p <= r; p++) {
if (r % p != 0) continue;
bool prime = true;
for (long long d = 2; d * d <= p; d++) if (p % d == 0) { prime = false; break; }
if (prime) dfs(x * p, sum + x * p, h + 1);
}
}
void sub1() {
if (b % a != 0) { cout << -1; return; }
best = LLONG_MAX;
dfs(a, a, 1);
cout << bestH << " " << best;
}
// Sub 2: phân tích b/a ra thừa số nguyên tố, nhân các số nguyên tố từ nhỏ đến lớn
void sub2() {
if (b % a != 0) { cout << -1; return; }
long long r = b / a;
vector<long long> f; // các thừa số nguyên tố (có lặp), tăng dần
for (long long p = 2; p * p <= r; p++)
while (r % p == 0) { f.push_back(p); r /= p; }
if (r > 1) f.push_back(r);
long long cur = a, sum = a;
for (long long p : f) { cur *= p; sum += cur; }
cout << f.size() + 1 << " " << sum;
}
int main() {
freopen("TOWER.INP", "r", stdin);
freopen("TOWER.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> a >> b;
if (b % a == 0 && b / a <= 10000) sub1();
else sub2();
}
Bình luận