Hướng dẫn giải của Dãy số đẹp (đề chọn HSG QG Tuyên Quang 2024)
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 xóa ít nhất phần tử để số ước của các phần tử còn lại tăng dần (tăng ngặt), tức là tìm dãy con tăng ngặt dài nhất của dãy ~d(a_i)~ (số ước của ~a_i~). Khó khăn nằm ở hai việc: đếm ước nhanh cho ~a_i \le 10^9~ và LIS nhanh cho ~n~ lớn.
Sub 1: Vét cạn — ~O(n \sqrt{a} + n^2)~, dùng khi ~n \le 1000~, ~a \le 10^6~
Đếm ước mỗi số bằng cách duyệt ~d~ đến ~\sqrt{a}~ (cặp ~d, a/d~), rồi tính LIS bằng quy hoạch động ~f[i] = 1 + \max f[j]~ với ~j < i~, ~d_j < d_i~. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: Sàng + LIS ~O(n \log n)~ — dùng khi ~a \le 10^6~
Sàng ước nguyên tố nhỏ nhất đến ~\max a~ để phân tích thừa số mỗi số trong ~O(\log a)~, số ước là tích ~(e_i + 1)~. LIS tăng ngặt bằng mảng ~t~ và lower_bound (với ngặt thì dùng lower_bound, không dùng upper_bound). Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 3: ~a \le 10^9~, ~n \le 5 \cdot 10^5~
Không thể sàng đến ~10^9~, cũng không nên chia thử đến ~\sqrt{a} \approx 31623~ cho mọi số. Chia thử chỉ các số nguyên tố ~\le 1000~ (căn bậc ba của ~10^9~). Phần còn lại ~r~ không có ước nguyên tố nhỏ hơn 1000 nên có tối đa 2 thừa số nguyên tố: ~r = 1~ (nhân 1), ~r~ nguyên tố (nhân 2, kiểm tra bằng Miller-Rabin), ~r = p^2~ (nhân 3, kiểm tra chính phương), còn lại ~r = pq~ (nhân 4). Sau đó LIS ~O(n \log n)~ như sub 2. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file Daysodep.inp/Daysodep.out); nếu ~n \le 1000~ và ~a \le 10^6~ gọi sub1, nếu ~a \le 10^6~ gọi sub2, ngược 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. Kết quả: 20/20 test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int a[500005], tau[500005];
// độ dài dãy con tăng ngặt dài nhất của tau[] theo O(n log n)
int lis() {
vector<int> t;
for (int i = 0; i < n; i++) {
auto it = lower_bound(t.begin(), t.end(), tau[i]);
if (it == t.end()) t.push_back(tau[i]); else *it = tau[i];
}
return t.size();
}
// Sub 1: đếm ước bằng duyệt đến căn, LIS quy hoạch động O(n^2) — dùng khi n <= 1000, a <= 10^6
void sub1() {
for (int i = 0; i < n; i++) {
int c = 0;
for (int d = 1; (ll)d * d <= a[i]; d++)
if (a[i] % d == 0) c += (d * d == a[i]) ? 1 : 2;
tau[i] = c;
}
vector<int> f(n, 1);
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) if (tau[j] < tau[i]) f[i] = max(f[i], f[j] + 1);
best = max(best, f[i]);
}
cout << best << "\n";
}
// Sub 2: sàng ước nguyên tố nhỏ nhất đến 10^6, đếm ước nhanh, LIS O(n log n) — dùng khi a <= 10^6
void sub2() {
int M = *max_element(a, a + n);
vector<int> spf(M + 1, 0);
for (int i = 2; i <= M; i++)
if (!spf[i]) for (int j = i; j <= M; j += i) if (!spf[j]) spf[j] = i;
for (int i = 0; i < n; i++) {
int x = a[i], c = 1;
while (x > 1) {
int p = spf[x], e = 0;
while (x % p == 0) x /= p, e++;
c *= e + 1;
}
tau[i] = c;
}
cout << lis() << "\n";
}
ull mulmod(ull x, ull y, ull m) { return x * y % m; }
ull pw(ull b, ull e, ull m) { ull r = 1; b %= m; while (e) { if (e & 1) r = mulmod(r, b, m); b = mulmod(b, b, m); e >>= 1; } return r; }
// Miller-Rabin cho số < 2^32
bool isPrime(ull x) {
if (x < 2) return false;
for (ull p : {2, 3, 5, 7}) { if (x % p == 0) return x == p; }
ull d = x - 1; int s = 0;
while (d % 2 == 0) d /= 2, s++;
for (ull b : {2, 3, 5, 7}) {
ull y = pw(b, d, x);
if (y == 1 || y == x - 1) continue;
bool ok = false;
for (int r = 1; r < s && !ok; r++) { y = mulmod(y, y, x); if (y == x - 1) ok = true; }
if (!ok) return false;
}
return true;
}
// Sub 3: a đến 10^9, n đến 5*10^5. Chia thử các số nguyên tố <= 10^3 (căn bậc ba của 10^9);
// phần còn lại r có tối đa 2 thừa số nguyên tố > 10^3: r = 1, p, p^2 hoặc p*q.
void sub3() {
vector<int> pr;
for (int i = 2; i <= 1000; i++) {
bool ok = true;
for (int p : pr) if (p * p <= i && i % p == 0) { ok = false; break; }
if (ok) pr.push_back(i);
}
for (int i = 0; i < n; i++) {
ll x = a[i], c = 1;
for (int p : pr) {
if (x % p) continue;
int e = 0;
while (x % p == 0) x /= p, e++;
c *= e + 1;
}
if (x > 1) {
ll r = llround(sqrtl((long double)x));
if (r * r == x) c *= 3;
else if (isPrime(x)) c *= 2;
else c *= 4;
}
tau[i] = c;
}
cout << lis() << "\n";
}
int main() {
freopen("Daysodep.inp", "r", stdin);
freopen("Daysodep.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int M = *max_element(a, a + n);
if (n <= 1000 && M <= 1000000) sub1();
else if (M <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận