Cặp số (HSG Tin THPT Thanh Hóa 2025, Câu 1)

Nguồn: Đề HSG Tin học THPT tỉnh Thanh Hóa 2025 – 2026 (Câu 1) Độ khó: Dễ Hằng đẳng thức Sàng nguyên tố

Đề bài

Cho 2 số nguyên dương $L, R$.

Yêu cầu: đếm số cặp số nguyên $(a, b)$ thỏa mãn:

• $L \le a < b \le R$;
• $b^2 - a^2$ là một số nguyên tố.

Dữ liệu vào: vào từ tệp CAU1.INP gồm 2 số nguyên dương $L, R$ $(L < R \le 2 \cdot 10^5)$.

Kết quả: ghi ra tệp CAU1.OUT một số nguyên là số cặp số thỏa mãn tìm được.

Ràng buộc: có $80\%$ số điểm có $R \le 500$; $20\%$ số điểm còn lại không có ràng buộc gì thêm.

Giới hạn: thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – input

5 13

Ví dụ – output

5

Giải thích ví dụ: 5 cặp là $(5, 6), (6, 7), (8, 9), (9, 10), (11, 12)$ với $b^2 - a^2$ lần lượt bằng $11, 13, 17, 19, 23$ – đều là số nguyên tố.

Lưu ý nộp bài: đề gốc đọc/ghi tệp CAU1.INP / CAU1.OUT, trên CLUE OJ bài này đọc bàn phím – in màn hình. Code C++ dùng if (fopen("CAU1.INP", "r")) { freopen(...); freopen(...); } nên nộp chỗ nào cũng được.

Lời mở đầu

Thoạt nhìn phải xét mọi cặp $(a, b)$ – khoảng $2 \cdot 10^{10}$ cặp với $R = 2 \cdot 10^5$. Nhưng chỉ cần một hằng đẳng thức quen thuộc của lớp 8, bài toán thu gọn còn một vòng lặp đơn, rồi thêm sàng Eratosthenes là xong. Đây là ví dụ rất đẹp cho việc "nghĩ toán trước khi code".

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test20 test, 2 mứcÝ tưởng(b − a)(b + a)Cách 1thử mọi cặpCách 2chỉ b = a + 1Cách 3+ sàngTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, khớp đúng 2 mức ràng buộc:

Test	L	R	Đáp án
1 – 16	2 … 294	7 … 458	0 … 154
17 – 20	1.492 … 135.434	3.812 … 151.867	0 … 16.703

• Test 20 có $L = 135\,434$, $R = 135\,439$ và đáp án $0$: trong đoạn ngắn này không có $2a + 1$ nào nguyên tố.

Subtask	Điều kiện	Các test	Cách ăn được
1 (80%)	$R \le 500$	1 – 16	Cách 1, 2, 3
2 (20%)	$R \le 2 \cdot 10^5$	17 – 20	Cách 2, 3

Ý tưởngb² − a² = (b − a)(b + a)

Theo hằng đẳng thức, $b^2 - a^2 = (b - a)(b + a)$ với $b - a \ge 1$ và $b + a > b - a$. Một số nguyên tố chỉ có hai ước dương là $1$ và chính nó, nên tích này nguyên tố khi và chỉ khi thừa số nhỏ bằng $1$:

Kết luận

$$b^2 - a^2 \text{ nguyên tố} \iff b - a = 1 \text{ và } b + a = 2a + 1 \text{ nguyên tố}$$

Vậy đáp án = số giá trị $a$ trong $[L, R - 1]$ mà $2a + 1$ là số nguyên tố.

Kiểm tra với ví dụ: $a$ chạy từ $5$ tới $12$, $2a + 1$ lần lượt là $11, 13, 15, 17, 19, 21, 23, 25$ – có 5 số nguyên tố. Em nhập $L, R$ rồi bấm Tiếp:

L = R =

Ví dụ nhanh:

Cách 1Thử mọi cặp (a, b)

Làm đúng theo đề: hai vòng lặp chọn $a < b$, tính $b^2 - a^2$ và kiểm tra nguyên tố bằng thử chia. Nhớ dùng long long vì $b^2$ có thể tới $4 \cdot 10^{10}$.

C++▶ Chạy tay từng dòng codeCách 1: hai vòng lặp chọn L ≤ a < b ≤ R, kiểm tra b² − a² nguyên tố.

Dữ liệu vào (stdin) – sửa thoải mái5 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Có khoảng $\frac{(R-L)^2}{2}$ cặp, mỗi cặp tốn thêm $O(\sqrt{b^2 - a^2}) = O(R)$ trong trường hợp xấu. Với $R \le 500$ vẫn ổn; với $R = 2 \cdot 10^5$ thì chỉ chạy kịp khi đoạn $[L, R]$ rất ngắn (bộ test có 2 test như vậy ở subtask 2).

Không gian$O(1)$

Thời gian$O(R^2 \cdot R)$ trong trường hợp xấu

Kết quả chạy thật: bản C++ đúng 18/20 test (Subtask 1: 16/16, Subtask 2: 2/4), test đúng chạy lâu nhất 0,677 giây; 2 test quá thời gian; bản Python đúng 17/20 test (Subtask 1: 16/16, Subtask 2: 1/4), test đúng chạy lâu nhất 0,128 giây; 3 test quá thời gian.

Cách 2Chỉ xét b = a + 1, kiểm tra 2a + 1 nguyên tố

Dùng kết luận ở phần Ý tưởng: một vòng lặp $a$ từ $L$ tới $R - 1$, đếm các $a$ có $2a + 1$ nguyên tố (thử chia tới $\sqrt{2a + 1}$).

C++▶ Chạy tay từng dòng codeCách 2: một vòng lặp a từ L tới R − 1, kiểm tra 2a + 1 nguyên tố bằng thử chia.

Dữ liệu vào (stdin) – sửa thoải mái5 13

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• $R - L$ lần kiểm tra, mỗi lần tối đa $\sqrt{4 \cdot 10^5} \approx 632$ phép chia: cỡ $10^8$ trong trường hợp xấu nhất nhưng thực tế ít hơn nhiều vì đa số số lẻ có ước nhỏ.

Không gian$O(1)$

Thời gian$O((R - L)\sqrt R)$

Kết quả chạy thật: bản C++ đúng 20/20 test (Subtask 1: 16/16, Subtask 2: 4/4), test đúng chạy lâu nhất 0,092 giây; bản Python đúng 19/20 test (Subtask 1: 16/16, Subtask 2: 3/4), test đúng chạy lâu nhất 0,398 giây; 1 test quá thời gian.

Cách 3Sàng Eratosthenes tới 2R

Vì $2a + 1 \le 2(R - 1) + 1 < 2R$, ta sàng sẵn mọi số tới $2R$ rồi tra mảng trong $O(1)$ cho mỗi $a$.

C++▶ Chạy tay từng dòng codeCách 3: sàng Eratosthenes tới 2R, rồi đếm các a có np[2a + 1] = false.

Dữ liệu vào (stdin) – sửa thoải mái5 13

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Sàng tới $4 \cdot 10^5$ tốn $O(R \log\log R)$, sau đó mỗi $a$ chỉ tra mảng.

Không gian$O(R)$

Thời gian$O(R \log\log R)$

Kết quả chạy thật: bản C++ đúng 20/20 test (Subtask 1: 16/16, Subtask 2: 4/4), test đúng chạy lâu nhất 0,005 giây; bản Python đúng 20/20 test (Subtask 1: 16/16, Subtask 2: 4/4), test đúng chạy lâu nhất 0,056 giây.

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

Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 20 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–16	Subtask 2 test 17–20	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	16/16	2/4	18/20	0,677s
Cách 1 – Python	16/16	1/4	17/20	0,128s
Cách 2 – C++	16/16	4/4	20/20	0,092s
Cách 2 – Python	16/16	3/4	19/20	0,398s
Cách 3 – C++	16/16	4/4	20/20	0,005s
Cách 3 – Python	16/16	4/4	20/20	0,056s

Ghi chú của mình: cả 3 cách đều cho đáp án đúng ở mọi test chạy kịp. Chỉ một dòng biến đổi $b^2 - a^2 = (b - a)(b + a)$ đã đưa bài toán từ hai vòng lặp về một vòng lặp: cách 2 bản C++ đã đủ 20/20 (bản Python hụt 1 test lớn), còn cách 3 thêm sàng Eratosthenes thì cả C++ lẫn Python đều chạy tức thì. Bài học: gặp hiệu hai bình phương, hãy nghĩ ngay tới hằng đẳng thức – tích hai số nguyên dương là số nguyên tố thì một thừa số phải bằng 1.

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 😇