Bảng vuông gần nguyên tố (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B, C1, C2)

Nguồn: Tin học trẻ 2025 – Vòng loại QG đợt 1 – Bảng B, C1, C2 Độ khó: Trung bình Sàng Eratosthenes Cộng dồn 2 chiều Chặt nhị phân

Đề bài

Cho lưới ô vuông $A$ gồm $m$ dòng (đánh số $1..m$ từ trên xuống) và $n$ cột (đánh số $1..n$ từ trái sang). Ô ở dòng $i$, cột $j$ gọi là ô $(i, j)$ và chứa một số nguyên không âm $a_{i,j} \le 10^6$.

Một hình vuông gồm các ô của lưới được gọi là bảng vuông gần nguyên tố nếu trong đó có không quá một ô chứa số không phải số nguyên tố (nhớ rằng $0$ và $1$ cũng không phải số nguyên tố).

Hãy tìm bảng vuông gần nguyên tố có diện tích lớn nhất và cho biết nó gồm bao nhiêu ô.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương $m, n$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số $a_{i,1}, a_{i,2}, \dots, a_{i,n}$.

Kết quả: một số nguyên là số ô của bảng vuông gần nguyên tố lớn nhất.

Subtask: mỗi subtask 25% số test.

• Subtask 1: $m, n \le 10$.
• Subtask 2: $m, n \le 50$.
• Subtask 3: $m, n \le 300$.
• Subtask 4: $m \times n \le 10^6$.

Giới hạn thời gian: 0,1 giây (rất chặt!), bộ nhớ: 1 GB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B, C1, C2. Đề được mình viết lại cho dễ đọc.

Ví dụ – input

3 4
1 2 3 4
1 3 5 7
2 4 6 8

Ví dụ – output

4

Giải thích: hình vuông $2 \times 2$ gồm các ô $(1,2),$ $(1,3),$ $(2,2),$ $(2,3)$ chứa $2, 3, 3, 5$ – toàn số nguyên tố. Mọi hình vuông $3 \times 3$ (chỉ có 2 cái: cột 1–3 và cột 2–4) đều chứa ít nhất hai số không nguyên tố ($1, 1, 4, 6, 8, \dots$) nên đáp án là $2 \times 2 = 4$ ô.

Lời mở đầu

Bài này là "tổ hợp" của 3 kỹ thuật rất cơ bản mà bạn nào học thuật toán cũng phải nắm: sàng Eratosthenes (kiểm tra nguyên tố thật nhanh), mảng cộng dồn 2 chiều (đếm số ô "xấu" trong một hình vuông bằng $O(1)$) và chặt nhị phân theo đáp án. Mình sẽ đi từ vét cạn (ăn subtask 1, 2) rồi lần lượt thêm từng kỹ thuật cho tới khi trọn điểm, cuối cùng là một mẹo nhỏ đưa thuật toán về $O(m \cdot n)$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test24 testÝ tưởngcộng dồnCách 1vét cạnCách 2sàng + cộng dồnCách 3chặt nhị phânCách 4O(mn)

Bộ testBộ test có gì?

Bộ test trên CLUE gồm 24 test (mình tự sinh theo đúng ràng buộc của đề, mỗi subtask 6 test). Mình đã kiểm tra kích thước từng test đúng với subtask của nó. Lời giải cách 3 (chặt nhị phân, đọc nhanh bằng fread) mình đã nộp trên bộ chấm chính thức tinhoctre.vn và được 100 điểm.

Nhóm	Test	$m$ lớn nhất	$n$ lớn nhất	Số ô lớn nhất	Số ô không nguyên tố	Đáp án
Subtask 1	1–6	10	10	100	0 – 100	1 – 100
Subtask 2	7–12	50	50	2.500	1 – 1.107	1 – 2.500
Subtask 3	13–18	300	300	90.000	0 – 17.671	49 – 90.000
Subtask 4	19–24	1.000.000	1.000.000	1.000.000	0 – 500.201	1 – 998.001

• Có test toàn số nguyên tố (test 3, 17 – đáp án là cả lưới vuông), test toàn hợp số (test 4 – đáp án 1), test 8 chỉ có đúng 1 ô xấu (đáp án $50 \times 50 = 2500$), test 24 lưới $1000 \times 1000$ toàn nguyên tố trừ 2 góc đối diện (đáp án $999^2$).
• Test 20, 21 là lưới "dẹt" $1 \times 10^6$ và $10^6 \times 1$ – đáp án luôn là 1 nhưng vẫn phải đọc hết $10^6$ số.
• Các số "bẫy": $0$, $1$, bình phương số nguyên tố ($4, 9, 994009 = 997^2$), số Carmichael ($561, 1105$)... đều không phải số nguyên tố.
• Test lớn nặng khoảng 6,5 MB – riêng việc đọc dữ liệu đã chiếm phần lớn 0,1 giây, nên các cách cuối đọc bằng fread.

Kết quả chạy thật (C++) của các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1	Cách 2	Cách 3	Cách 4
Subtask 1 (25%)	$m, n \le 10$	1–6	6/6	6/6	6/6	6/6
Subtask 2 (25%)	$m, n \le 50$	7–12	6/6	6/6	6/6	6/6
Subtask 3 (25%)	$m, n \le 300$	13–18	1/6	6/6	6/6	6/6
Subtask 4 (25%)	$m \times n \le 10^6$	19–24	0/6	2/6	6/6	6/6

Ý tưởngĐếm ô "xấu" nhanh và chặt nhị phân cạnh

Gọi ô chứa số không nguyên tố là ô xấu, đặt $b_{i,j} = 1$ nếu ô $(i,j)$ xấu, ngược lại $0$. Bài toán thành: tìm hình vuông lớn nhất có tổng $b$ bên trong $\le 1$. Ba ý chính:

1. Sàng Eratosthenes tới $10^6$ một lần → biết ngay số nào nguyên tố trong $O(1)$.
2. Cộng dồn 2 chiều: $P_{i,j}$ = số ô xấu trong hình chữ nhật từ $(1,1)$ tới $(i,j)$: $$P_{i,j} = P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1} + b_{i,j}.$$ Khi đó số ô xấu của hình vuông cạnh $k$ có góc dưới-phải $(i,j)$ là $$c = P_{i,j} - P_{i-k,j} - P_{i,j-k} + P_{i-k,j-k}.$$
3. Tính đơn điệu: nếu có hình vuông cạnh $k$ hợp lệ thì bỏ đi một hàng và một cột ta được hình vuông cạnh $k - 1$ nằm trong nó, số ô xấu chỉ có thể giảm → cũng hợp lệ. Vậy "có hình vuông cạnh $k$ hợp lệ không?" có dạng Đúng, Đúng, ..., Đúng, Sai, ..., Sai → chặt nhị phân được.

Em nhập lưới (các dòng cách nhau bởi dấu /) rồi bấm Tiếp để xem chặt nhị phân thử từng cạnh $k$. Ô đỏ là ô xấu:

Lưới:

Ví dụ nhanh:

Cách 1Vét cạn mọi hình vuông

Thử mọi góc trên-trái $(i, j)$, mọi cạnh $k$, rồi đếm trực tiếp số ô xấu trong hình vuông bằng 2 vòng lặp. Kiểm tra nguyên tố bằng cách thử chia tới $\sqrt{a}$.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi hình vuông, đếm trực tiếp số ô xấu.

Dữ liệu vào (stdin) – sửa thoải mái3 4 1 2 3 4 1 3 5 7 2 4 6 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Số hình vuông cỡ $O(m \cdot n \cdot \min(m,n))$, mỗi hình đếm mất $O(k^2)$ → tổng khoảng $O(m \cdot n \cdot \min(m,n)^3)$. Với $m = n = 50$ là khoảng $10^7$ phép tính – vẫn kịp; với $300$ thì không.
2. Hàm isPrime thử chia tới $\sqrt{a} \approx 1000$: với $10^6$ ô là $10^9$ phép chia – cũng quá chậm ở subtask 4, kể cả khi lưới chỉ là $1 \times 10^6$.

Không gian$O(mn)$

Thời gian$O(mn \cdot \min(m,n)^3 + mn\sqrt{V})$

Kết quả chạy thật: bản C++ đúng 13/24 test, quá thời gian test 13–17, 19–24 (các test đúng chạy lâu nhất 0.012s). Qua subtask 1, 2 và test 18 ($300 \times 7$, cạnh tối đa 7). Bản Python đúng 7/24 test, quá thời gian test 7–10, 12–24 (các test đúng chạy lâu nhất 0.036s).

Cách 2Sàng + cộng dồn, thử mọi cạnh

Thay 2 chỗ chậm của cách 1: dùng sàng để biết số nào nguyên tố, và dùng mảng cộng dồn để đếm số ô xấu của một hình vuông trong $O(1)$. Lúc này mình chọn $(i, j)$ là góc dưới-phải cho công thức gọn. Từ cách này trở đi mình đọc dữ liệu bằng fread (nạp cả file vào bộ nhớ rồi tự tách số) vì với giới hạn 0,1 giây, cin đọc $10^6$ số đã tốn gần hết thời gian.

C++▶ Chạy tay từng dòng codeCách 2: sàng + mảng cộng dồn, thử mọi góc dưới-phải và mọi cạnh.

Dữ liệu vào (stdin) – sửa thoải mái3 4 1 2 3 4 1 3 5 7 2 4 6 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Mảng $P$ kích thước $(m+1) \times (n+1)$ được "duỗi" thành mảng 1 chiều: phần tử $P_{i,j}$ nằm ở vị trí i * W + j với W = n + 1. Lưới $10^6 \times 1$ mà khai báo vector<vector<int>> sẽ tạo một triệu vector nhỏ – rất chậm.
2. Hàng $0$ và cột $0$ của $P$ bằng $0$ giúp công thức không phải xét riêng biên.

Không gian$O(mn + V)$

Thời gian$O(mn \cdot \min(m,n) + V \log\log V)$

Kết quả chạy thật: bản C++ đúng 20/24 test, quá thời gian test 19, 22–24 (các test đúng chạy lâu nhất 0.035s). Qua 3 subtask đầu, nhưng các lưới $1000 \times 1000$ và $500 \times 2000$ của subtask 4 cần cỡ $10^9$ phép thử nên quá thời gian.

Cách 3Chặt nhị phân cạnh – O(mn log)

Dùng tính đơn điệu ở phần ý tưởng: viết hàm ok(k) kiểm tra có hình vuông cạnh $k$ hợp lệ không (duyệt mọi góc, mỗi góc $O(1)$), rồi chặt nhị phân tìm $k$ lớn nhất có ok(k) đúng. Cạnh $1$ luôn hợp lệ (1 ô thì có nhiều nhất 1 ô xấu) nên bắt đầu với lo = 1.

C++▶ Chạy tay từng dòng codeCách 3: chặt nhị phân cạnh k, hàm ok(k) kiểm tra bằng mảng cộng dồn.

Dữ liệu vào (stdin) – sửa thoải mái3 4 1 2 3 4 1 3 5 7 2 4 6 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. mid = (lo + hi + 1) / 2 (làm tròn lên) vì nhánh đúng gán lo = mid; làm tròn xuống thì khi hi = lo + 1 sẽ lặp vô hạn.
2. ok(k) dừng ngay khi thấy một hình vuông hợp lệ (return true), nên thường chạy rất nhanh.
3. Đáp án là số ô $k^2$ chứ không phải cạnh $k$ – có thể tới $10^6$, ép kiểu long long cho chắc.

Không gian$O(mn + V)$

Thời gian$O(mn \log \min(m,n) + V \log\log V)$

Kết quả chạy thật: bản C++ đúng 24/24 test, chạy lâu nhất 0.033s. Full điểm – đây là cách mình đã nộp trên tinhoctre.vn (100 điểm). Bản Python đúng 17/24 test, quá thời gian test 16, 19–24 (các test đúng chạy lâu nhất 0.074s) – Python không thể đọc và xử lý $10^6$ số trong 0,1 giây.

Cách 4Chỉ thử cạnh lớn hơn best – O(mn)

Một mẹo nhỏ nữa, không cần chặt nhị phân. Quay lại cách 2 (góc dưới-phải $(i,j)$, thử cạnh $k$), nhưng:

• ta chỉ quan tâm các cạnh lớn hơn kỷ lục best hiện tại → bắt đầu từ k = best + 1;
• nếu cạnh $k$ đã hỏng thì cạnh $k+1$ (cùng góc dưới-phải, chứa hình vuông cạnh $k$) chắc chắn hỏng → break ngay.

Mỗi lần thử hoặc làm best tăng 1 (tổng cộng không quá $\min(m,n)$ lần), hoặc break (mỗi ô 1 lần) → tổng $O(m \cdot n)$.

C++▶ Chạy tay từng dòng codeCách 4: chỉ thử cạnh lớn hơn best, hỏng thì break – O(mn).

Dữ liệu vào (stdin) – sửa thoải mái3 4 1 2 3 4 1 3 5 7 2 4 6 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(mn + V)$

Thời gian$O(mn + V \log\log V)$

Kết quả chạy thật: bản C++ đúng 24/24 test, chạy lâu nhất 0.061s. Bản Python đúng 18/24 test, quá thời gian test 19–24 (các test đúng chạy lâu nhất 0.073s). Về lý thuyết nhanh hơn cách 3, nhưng thực tế cả hai đều bị chi phối bởi việc đọc 6,5 MB dữ liệu nên thời gian xấp xỉ nhau.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Vét cạn + thử chia	C++	13/24	0.012s	quá giờ 13–17, 19–24 – subtask 1, 2
	Python	7/24	0.036s	quá giờ 7–10, 12–24
2. Sàng + cộng dồn, thử mọi cạnh	C++	20/24	0.035s	quá giờ 19, 22–24 – subtask 1–3
3. Chặt nhị phân cạnh	C++	24/24	0.033s	Đúng hết
	Python	17/24	0.074s	quá giờ 16, 19–24
4. Chỉ thử cạnh lớn hơn best	C++	24/24	0.061s	Đúng hết
	Python	18/24	0.073s	quá giờ 19–24

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình, giới hạn 0,1 giây. Hai cách cuối (C++) đều qua hết; Python chỉ đọc dữ liệu thôi đã vượt 0,1 giây ở các test lớn nên chỉ ăn được một phần (mình vẫn để code Python để các bạn tham khảo cách làm). Bài học: sàng + cộng dồn + chặt nhị phân theo đáp án là bộ ba "kinh điển", và với giới hạn thời gian chặt thì nhớ đọc dữ liệu nhanh.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇