Hướng dẫn giải của [Beginner Free Contest 05] LCMSEQ
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 chia ~n~ thành tổng các số dương sao cho bội chung nhỏ nhất (BCNN) của chúng lớn nhất (hàm Landau). Kết quả có thể vượt ~2^{63}~ nên phải dùng unsigned long long.
Sub 1: Vét cạn — dùng khi ~n \le 60~
Duyệt mọi cách chia ~n~ thành các phần tăng dần (phần bằng nhau thì bỏ bớt không đổi BCNN, phần thừa coi như số 1), cập nhật BCNN lớn nhất. Số cách chia tăng nhanh nên chỉ chạy kịp với ~n~ nhỏ. Nếu chỉ nộp sub này: đúng 15/50 test.
Sub 2: Quy hoạch động trên lũy thừa nguyên tố — ~O(n \cdot \pi(n) \cdot \log n)~
Để BCNN lớn nhất, các phần nên đôi một nguyên tố cùng nhau, và tốt nhất là mỗi phần là một lũy thừa của một số nguyên tố khác nhau (~p^k~). Do đó với mỗi số nguyên tố ta chọn tối đa một lũy thừa của nó (hoặc không chọn), tổng các lũy thừa không quá ~n~, tích lớn nhất. Đây là bài cái túi nhóm: ~dp[s]~ là tích lớn nhất với tổng không quá ~s~. Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Hàm main đọc ~n~; ~n \le 60~ 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 n;
unsigned long long best;
// Sub 1: vét cạn mọi cách chia n thành các phần phân biệt, dùng khi n <= 60
// (nếu dãy có hai số bằng nhau, bỏ bớt một số không đổi BCNN, phần dư thay bằng số 1)
void dfs(int rest, int minPart, unsigned long long l) {
best = max(best, l);
for (int x = minPart; x <= rest; x++)
dfs(rest - x, x + 1, l / __gcd(l, (unsigned long long)x) * x);
}
void sub1() {
best = 1;
dfs(n, 1, 1);
printf("%llu\n", best);
}
// Sub 2: BCNN lớn nhất đạt được khi các phần là lũy thừa nguyên tố của các số nguyên tố khác nhau
// Quy hoạch động kiểu cái túi: dp[s] = tích lớn nhất với tổng <= s, mỗi số nguyên tố chọn tối đa 1 lũy thừa
void sub2() {
vector<unsigned long long> dp(n + 1, 1);
for (int p = 2; p <= n; p++) {
bool prime = true;
for (int d = 2; d * d <= p; d++) if (p % d == 0) prime = false;
if (!prime) continue;
for (int s = n; s >= 0; s--) {
unsigned long long pw = p;
while (pw <= s) {
dp[s] = max(dp[s], dp[s - (int)pw] * pw);
pw *= p;
}
}
}
printf("%llu\n", dp[n]);
}
int main() {
scanf("%d", &n);
if (n <= 60) sub1();
else sub2();
return 0;
}
Bình luận