Tập chia hết (Ver 2)
Đề bài
Cho tập số nguyên dương $S = \{a_1, a_2, \ldots, a_n\}$. Hãy tìm một tập con $D$ của $S$ gồm nhiều số nhất mà hai phần tử $x, y$ bất kì thuộc tập $D$ thì hoặc là $x$ chia hết cho $y$ hoặc là $y$ chia hết cho $x$.
Dữ liệu:
- Dòng đầu chứa số nguyên dương $n$;
- Dòng tiếp theo chứa $n$ số nguyên dương mô tả tập $S$ (các số không vượt quá $10^{18}$).
Kết quả: ghi ra một số là lực lượng (số phần tử) của tập $D$ tìm được.
Ràng buộc:
- 20% số test đầu tiên có $n \le 20$;
- 20% số test tiếp theo có $n \le 10^2$;
- 20% số test tiếp theo có $n \le 10^3$;
- 20% số test tiếp theo có $n \le 10^4$;
- 20% số test cuối cùng có $n \le 10^6$ và các số trong tập $S$ không vượt quá $4 \cdot 10^5$.
Giới hạn trên CLUE OJ: 5 giây, 256 MB.
4
6 9 12 33Giải thích ví dụ: chọn $D = \{3, 6, 12\}$: $6 \vdots 3$, $12 \vdots 3$, $12 \vdots 6$. Không thể lấy thêm $9$ vì $9$ và $6$ không chia hết cho nhau.
Lời mở đầu
Thoạt nhìn bài này giống bài "tìm tập con", nhưng chỉ cần sắp xếp lại là nó biến thành người anh em của bài kinh điển dãy con tăng dài nhất. Mình sẽ đi từ vét cạn (20%), lên QHĐ $O(n^2)$ (80%), rồi tận dụng giới hạn $a_i \le 4 \cdot 10^5$ của subtask cuối để làm QHĐ trên giá trị kiểu sàng ước – bội, ăn trọn 100%.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | $n$ | $a_i$ lớn nhất | Test có số trùng | Đáp án |
|---|---|---|---|---|
| 1–20 | 4 … 20 | 50 | 14/20 | 2 … 7 |
| 21–40 | 100 | ≈ 1,00 · 1018 | 15/20 | 2 … 7 |
| 41–60 | 1.000 | ≈ 1,00 · 1018 | 20/20 | 23 … 44 |
| 61–80 | 10.000 | ≈ 1,00 · 1018 | 20/20 | 254 … 304 |
| 81–90 | 100.000 | 399.972 | 10/10 | 25.586 … 25.890 |
| 91–100 | 1.000.000 | 399.996 | 10/10 | 257.136 … 1.000.000 |
Bộ test chia đúng 5 subtask, mỗi subtask 20 test. Hai điều rất quan trọng rút ra từ bộ test:
- Có số trùng nhau (gần như test nào cũng có, kể cả số 1 lặp lại nhiều lần). Hai số bằng nhau thì chia hết cho nhau, nên được lấy cả hai – đáp án đếm cả các số trùng (có test đáp án lên tới $10^6$ = lấy hết). Lời giải của mình xử lý điều này tự nhiên, không cần làm gì thêm.
- Subtask 1–4: số lớn tới gần $10^{18}$ (phải dùng
long long), nhưng $n \le 10^4$. Subtask 5: $n$ tới $10^6$ nhưng mọi số $\le 4 \cdot 10^5$. Hai kiểu dữ liệu này cần hai cách tối ưu khác nhau.
| Subtask | Điều kiện | Test | Cách 1 (vét cạn) | Cách 2 (QHĐ $O(n^2)$) | Cách 3 (QHĐ trên giá trị) |
|---|---|---|---|---|---|
| 1 | $n \le 20$ | 1–20 | qua | qua | qua |
| 2 | $n \le 100$ | 21–40 | không chạy nổi | qua | qua |
| 3 | $n \le 10^3$ | 41–60 | không chạy nổi | qua | qua |
| 4 | $n \le 10^4$ | 61–80 | không chạy nổi | qua | qua |
| 5 | $n \le 10^6$, $a_i \le 4 \cdot 10^5$ | 81–100 | không chạy nổi | quá thời gian | qua |
Ý tưởngSắp xếp xong, tập chia hết là một "chuỗi"
Sắp xếp $D$ tăng dần: $d_1 \le d_2 \le \ldots \le d_k$. Điều kiện "đôi một chia hết" tương đương với: mỗi số chia hết cho số đứng ngay trước nó, tức $d_1 \mid d_2 \mid \ldots \mid d_k$.
- Chiều thuận: số lớn hơn chỉ có thể chia hết cho số nhỏ hơn (không thể ngược lại), nên $d_{t+1} \vdots d_t$.
- Chiều ngược: phép chia hết có tính bắc cầu – $d_1 \mid d_2$ và $d_2 \mid d_3$ thì $d_1 \mid d_3$. Nên chỉ cần các cặp đứng cạnh nhau chia hết là mọi cặp đều chia hết.
Vậy bài toán trở thành: sắp xếp $a$ tăng dần, tìm dãy con dài nhất mà phần tử sau chia hết cho phần tử trước – y hệt bài dãy con tăng dài nhất, chỉ thay điều kiện "$<$" bằng "chia hết".
Em nhập dãy rồi bấm Tiếp. Ô vàng là $dp[i]$ đang tính, các ô xanh tím là những $a_j$ chia hết $a_i$ (được dùng tới), ô mờ là $a_j$ không chia hết; bước cuối lần ngược ra tập $D$:
Cách 1Vét cạn mọi tập con (subtask 1)
Với $n \le 20$ ta thử cả $2^n$ tập con bằng bitmask. Nhờ nhận xét ở trên, sau khi sắp xếp, với mỗi tập con chỉ cần kiểm tra số được chọn sau chia hết cho số được chọn ngay trước (biến last) thay vì kiểm tra mọi cặp.
Kết quả chạy thật: bản C++ đúng 20/100 test – trọn subtask 1, chậm nhất 0,01 giây; bản Python cũng qua 20 test này (chậm nhất 0,55 giây). Từ test 21 trở đi $n \ge 100$: $2^{100}$ tập con là không thể duyệt (và cũng không biểu diễn được bằng một số int), nên 80 test còn lại đều sai.
Cách 2QHĐ $O(n^2)$ như dãy con tăng dài nhất (subtask 1–4)
Cài đặt đúng công thức $dp[i]$ ở phần ý tưởng. Mảng $a$ dùng long long vì số tới $10^{18}$.
- Phải sắp xếp trước: khi đó mọi ước của $a_i$ (khác $a_i$) đều đứng trước $i$, và các số bằng $a_i$ cũng có thể đứng trước – chúng chia hết nhau nên vẫn được nối vào chuỗi. Nhờ vậy số trùng được đếm đúng.
- Hai vòng lặp lồng nhau: $\frac{n(n-1)}{2}$ phép
%. Với $n = 10^4$ là $5 \cdot 10^7$ phép – chạy khoảng 0,16 giây. Với $n = 10^6$ là $5 \cdot 10^{11}$ phép – vô vọng.
Kết quả chạy thật: bản C++ đúng 80/100 test (subtask 1–4), chậm nhất 0,16 giây ở $n = 10^4$. 20 test subtask 5 ($n = 10^5$ và $10^6$) quá thời gian. Bản Python qua 60 test đầu (chậm nhất 0,06 giây); với $n = 10^4$ Python cần khoảng 3,8 giây – vẫn kịp giới hạn 5 giây của bài (xem kết quả cách 3).
Cách 3QHĐ trên giá trị – "đẩy" sang các bội (full điểm)
Ở subtask 5, $n$ rất lớn nhưng giá trị nhỏ ($\le 4 \cdot 10^5$). Ta đổi góc nhìn: thay vì QHĐ theo vị trí, ta QHĐ theo giá trị.
- Đếm
cnt[v]= số lần giá trị $v$ xuất hiện (các số bằng nhau luôn lấy hết cùng nhau). - Gọi $f[v]$ = số phần tử nhiều nhất của một chuỗi chia hết có số lớn nhất bằng $v$. Thì $f[v] = cnt[v] + \max\{ f[d] : d \mid v,\ d < v \}$.
- Thay vì đi tìm các ước của $v$ (khó), ta làm ngược lại: xét $v$ từ nhỏ đến lớn, khi đã có $f[v]$ thì "đẩy" nó sang mọi bội $m = 2v, 3v, \ldots$:
f[m] = max(f[m], f[v]). Đến lượt $m$, $f[m]$ đã chứa sẵn max của mọi ước, chỉ việc cộngcnt[m].
Số phép "đẩy" là $\frac{M}{1} + \frac{M}{2} + \ldots + \frac{M}{M} \approx M \ln M$ – với $M = 4 \cdot 10^5$ chỉ khoảng $5 \cdot 10^6$ phép, giống hệt sàng Eratosthenes. (Đẩy qua cả những giá trị không có trong tập cũng không sao: nhờ tính bắc cầu, chuỗi đi "vòng" qua $v$ vẫn đúng là chuỗi chia hết.)
Còn các test số lớn ($10^{18}$) thì $n \le 10^4$, ta dùng lại cách 2. Chương trình hoàn chỉnh chọn cách theo giá trị lớn nhất:
mx <= MAXV (số nhỏ). Nhánh else giống hệt cách 2. Ô xanh tím là bội m đang được cập nhật.Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,16 giây (test 78, nhánh $O(n^2)$ với $n = 10^4$); các test $n = 10^6$ chạy nhánh sàng rất nhanh. Bản Python cũng 100/100, chậm nhất 3,8 giây (test 75, nhánh $O(n^2)$) – sát nhưng vẫn dưới giới hạn 5 giây.
int cho các số tới $10^{18}$. Bộ test có rất nhiều số trùng nhau – các số bằng nhau chia hết cho nhau nên được lấy hết.