Số dư 2
Đề bài
Bạn được cho một dãy số nguyên dương $A = (a_1, a_2, \ldots, a_n)$.
Yêu cầu: hãy tìm giá trị lớn nhất của phần dư trong phép chia số nguyên $a_i$ cho $a_j$, với $1 \le i, j \le n$ và $a_i \ge a_j$.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên dương $n$ – độ dài của dãy $(1 \le n \le 200000)$.
- Dòng thứ hai chứa $n$ số nguyên lần lượt là $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^6)$, mỗi số cách nhau bởi một dấu cách.
Dữ liệu ra: một số nguyên là kết quả của bài toán.
Ràng buộc: $70\%$ số test có $n \le 5000$.
3
2 4 51Giải thích ví dụ: 4 chia 2 dư 0; 5 chia 2 dư 1; 5 chia 4 dư 1 (các phép chia một số cho chính nó dư 0). Kết quả số dư lớn nhất là 1.
Lời mở đầu
Đề bài ngắn gọn, cách "thử mọi cặp" ai cũng nghĩ ra và ăn ngay $70\%$ số điểm. Phần khó là $30\%$ còn lại với $n = 2 \cdot 10^5$: ta phải đổi góc nhìn từ "duyệt các cặp số" sang "duyệt các bội số của số chia", kết hợp một mảng tra cứu "số lớn nhất không vượt quá $x$" và một nhát cắt tỉa tham lam. Mình trình bày cả hai cách kèm kết quả chạy thật trên bộ test của CLUE.
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$ nhỏ nhất | $a_i$ lớn nhất | Số giá trị khác nhau | Đáp án |
|---|---|---|---|---|---|
| 1 – 20 | 5 … 10 | 1 … 6 | 44 … 97 | 4 … 9 | 2 … 39 |
| 21 – 70 | 5.000 | 1 | 996.235 … 999.997 | 3.039 … 3.197 | 496.338 … 499.801 |
| 71 – 100 | 200.000 | 1 | 999.940 … 999.999 | 69.744 … 70.608 | 499.933 … 499.996 |
- Bộ test có 100 test, khớp với ràng buộc của đề: 70 test đầu có $n \le 5000$ (test 1–20 chỉ có $n \le 10$, test 21–70 có đúng $n = 5000$), 30 test cuối có $n = 2 \cdot 10^5$.
- Từ test 21 trở đi các số trải rộng từ $1$ tới gần $10^6$, đáp án đều xấp xỉ $5 \cdot 10^5$ (gần bằng một nửa số lớn nhất – mình sẽ giải thích vì sao ở phần ý tưởng).
- Dãy có nhiều số trùng nhau: với $n = 2 \cdot 10^5$ chỉ còn khoảng $70\,000$ giá trị khác nhau.
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 (70%) | $n \le 5000$ | 1 – 70 | 70/70 | 20/70 | 70/70 | 70/70 |
| 2 (30%) | $n \le 2 \cdot 10^5$ | 71 – 100 | 0/30 | 0/30 | 30/30 | 30/30 |
Ý tưởngCố định số chia, chia trục số thành từng khối
Nhận xét 1. Cố định số chia $v = a_j$. Chia trục số thành các khối dài $v$: $[v, 2v - 1]$, $[2v, 3v - 1]$, $[3v, 4v - 1]$, ... Trong khối $[kv - v,\ kv - 1]$ thì $y \bmod v = y - (k - 1)v$, tức là số càng lớn thì số dư càng lớn. Vậy trong mỗi khối chỉ cần xét số lớn nhất của dãy nằm trong khối.
Nhận xét 2. "Số lớn nhất của dãy trong khối $[kv - v, kv - 1]$" chính là "số lớn nhất của dãy mà $\le kv - 1$" (nếu số này nhỏ hơn $kv - v$ thì nó thuộc khối trước, đã xét rồi – xét lại cũng không sai). Ta tính sẵn mảng
lon[x] = số lớn nhất trong dãy mà $\le x$, với lon[x] = x nếu $x$ có trong dãy, ngược lại lon[x] = lon[x − 1].
Khi đó với mỗi số chia $v$, ta chỉ đi qua các bội $2v, 3v, \ldots$ – khoảng $\dfrac{\max}{v}$ bước. Tổng trên mọi $v$ khác nhau là $\dfrac{\max}{1} + \dfrac{\max}{2} + \ldots$ $\approx \max \cdot \ln(\max)$ – chuỗi điều hoà.
Nhận xét 3 (cắt tỉa tham lam). Chia cho $v$ thì số dư không quá $v - 1$. Nếu duyệt $v$ từ lớn xuống nhỏ và gặp $v - 1 \le \text{ans}$ thì mọi số chia nhỏ hơn đều không thể cho kết quả tốt hơn → dừng luôn. Vì đáp án thường lớn – với dãy dày đặc, chỉ cần chọn số chia $v$ nhỉnh hơn $\frac{\max}{2}$ một chút thì $\max \bmod v = \max - v \approx \frac{\max}{2}$ (đó là lý do đáp án trong bộ test đều gần $5 \cdot 10^5$), ta chỉ phải xét các số chia lớn – mỗi số chỉ có vài bội. Đó là lý do chương trình chạy rất nhanh trên thực tế.
Em nhập dãy số (các số từ 1 đến 30) rồi bấm Tiếp để xem với từng số chia $v$, trục số được chia thành các khối thế nào và số dư lớn nhất lấy ở đâu:
Cách 1Thử mọi cặp – O(n²)
Hai vòng lặp lồng nhau thử mọi cặp $(i, j)$, chỉ lấy cặp có $a_i \ge a_j$.
- Điều kiện
a[i] >= a[j]đúng như đề. Khi $i = j$ số dư bằng 0 nên không ảnh hưởng. - Số cặp là $n^2$: với $n = 5000$ là $2{,}5 \cdot 10^7$ phép chia – rất nhanh; với $n = 2 \cdot 10^5$ là $4 \cdot 10^{10}$ – không thể chạy trong 1 giây.
Kết quả chạy thật: bản C++ đúng 70/100 test (quá thời gian ở test 71–100), test đúng chạy lâu nhất 0.107s; bản Python đúng 20/100 test (quá thời gian ở test 21–100), test đúng chạy lâu nhất 0.030s.
Cách 2Duyệt bội số + cắt tỉa
Cài đặt 3 nhận xét ở phần ý tưởng. Ta không cần giữ dãy, chỉ cần đánh dấu co[x] – giá trị $x$ có xuất hiện hay không (số trùng nhau tự động gộp lại).
lon[v] = co[v] ? v : lon[v - 1]: tính mảng "số lớn nhất $\le v$" bằng một vòng lặp từ trái sang phải.- Vòng
for(int k = 2 * v; k - v <= mx; k += v)đi qua từng khối $[k - v, k - 1]$ còn chạm tới số lớn nhấtmx;min(k - 1, mx)để không đọc ra ngoài mảng ở khối cuối. - Vì $v$ có trong dãy và $v \le k - 1$ nên
lon[min(k - 1, mx)]luôn $\ge v$ – điều kiện $a_i \ge a_j$ được đảm bảo. if(v - 1 <= ans) break;là nhát cắt tỉa: không có nó chương trình vẫn đúng và vẫn đủ nhanh ($\approx 10^6 \cdot \ln 10^6 \approx 1{,}4 \cdot 10^7$ bước), có nó thì chỉ phải xét vài số chia lớn nhất.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.036s; bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.460s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Thử mọi cặp | C++ | 70/100 | 0.107s | Quá thời gian ở test 71–100 |
| Python | 20/100 | 0.030s | Quá thời gian ở test 21–100 | |
| 2. Duyệt bội + mảng "lớn nhất ≤ x" | C++ | 100/100 | 0.036s | Full điểm |
| Python | 100/100 | 0.460s | Full điểm |
lon[] cũng là một dạng "cộng dồn" (prefix max) trên trục giá trị.