Ước chính phương

Nguồn: Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu 2022–2023 Độ khó: Trung bình Số học GCD

Đề bài

Bài 3. Ước chính phương

Số chính phương là một số nguyên dương bằng bình phương của một số nguyên dương khác. Như vậy các số sau được gọi là số chính phương: $1, 4, 9, 16, 25, \ldots$ Ta quan tâm các số nguyên dương $n$ tồn tại ước là một số chính phương lớn hơn 1. Các số đầu tiên thỏa điều kiện là: $4, 8,$ $9,$ $12,$ $16,$ $18,$ $20,$ $24,$ $\ldots$

Yêu cầu: Cho 2 số nguyên $L, R$ $(2 \le L < R \le 10^9)$. Đếm số lượng các cặp số nguyên $(a, b)$ sao cho $L \le a < b \le R$ và $a \times b$ có chứa ước là số chính phương lớn hơn 1.

Dữ liệu: Vào từ tập tin văn bản DSQUARE.INP chứa 2 số nguyên $L, R$ $(2 \le L < R \le 10^9;\ R - L \le 10^3)$.

Kết quả: Ghi ra tập tin văn bản DSQUARE.OUT số cặp thỏa yêu cầu.

Giới hạn: 1 giây, 256 MB. Trên CLUE OJ dữ liệu đọc/ghi với file theo tên như trong đề bài.

Ví dụ 1 – input

2 5

Ví dụ 1 – output

3

Ví dụ 2 – input

2 10

Ví dụ 2 – output

26

Giải thích:

• Ví dụ 1: $(2,4), (3,4), (4,5)$.
• Ví dụ 2: $(2,4),$ $(2,6),$ $(2,8),$ $(2,9),$ $(2,10),$ $(3,4),$ $(3,6),$ $(3,8),$ $(3,9),$ $(4,5),$ $(4,6),$ $(4,7),$ $(4,8),$ $(4,9),$ $(4,10),$ $(5,8),$ $(5,9),$ $(5,10),$ $(6,8),$ $(6,9),$ $(6,10),$ $(7,8),$ $(7,9),$ $(8,9),$ $(8,10),$ $(9,10)$.

Lời mở đầu

Đây là bài 3 trong đề tuyển sinh lớp 10 chuyên Tin trường Phổ thông Năng khiếu (TP.HCM) năm 2022–2023. Cái khó là $a \times b$ có thể lớn tới $10^{18}$, không thể phân tích trực tiếp. Mấu chốt là một nhận xét số học nhỏ giúp ta chỉ cần làm việc với từng số $a$, $b$ riêng lẻ. Mỗi cách mình trình bày đều được chạy thật trên 100 test của CLUE OJ.

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ộ test100 test, 5 nhómÝ tưởngPhi chính phương + gcdCách 1Vét cạn a×bCách 2Kiểm tra từng sốCách 3Tính trước

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

Đề không chia subtask và mọi test đều có $R - L \le 1000$ (số cặp tối đa khoảng $5 \cdot 10^5$). Thứ thay đổi giữa các test là độ lớn của $L, R$, nên mình tự chia 100 test thành 5 nhóm:

Nhóm	Test	L	R	R − L	Đáp án
Nhóm 1	1–10	2 – 18	7 – 31	1 – 19	0 – 146
Nhóm 2	11–30	405 – 9.791	1.405 – 10.791	1000 – 1000	354.592 – 358.873
Nhóm 3	31–60	10.808 – 42.051	11.808 – 43.051	1000 – 1000	353.536 – 360.653
Nhóm 4	61–80	1.000.734 – 10.031.324	1.001.734 – 10.032.324	1000 – 1000	355.202 – 358.167
Nhóm 5	81–100	100.002.987 – 999.999.000	100.003.987 – 1.000.000.000	1000 – 1000	355.348 – 358.694

Từ test 11 trở đi $R - L$ đều đúng bằng 1000 và đáp án luôn quanh mức $3{,}57 \cdot 10^5$ trên khoảng $5 \cdot 10^5$ cặp – tức là khoảng 71% số cặp thoả mãn. Test 100 là test "khủng" nhất với $R = 10^9$.

Ý tưởngKhi nào a × b có ước chính phương?

Gọi số không có ước chính phương nào lớn hơn 1 là số phi chính phương (squarefree), ví dụ $2, 3, 5, 6, 7, 10, \ldots$ Ta có:

• $a \times b$ có ước chính phương $k^2 > 1$ thì có ước $p^2$ với $p$ là một ước nguyên tố của $k$.
• $p^2 \mid a \times b$ nghĩa là số mũ của $p$ trong $a$ cộng số mũ của $p$ trong $b$ ít nhất là 2. Chỉ có 3 khả năng: $p^2 \mid a$, hoặc $p^2 \mid b$, hoặc $p$ chia hết cả $a$ lẫn $b$.

Mấu chốt

$a \times b$ có ước chính phương lớn hơn 1 $\iff$ $a$ không phi chính phương, hoặc $b$ không phi chính phương, hoặc $\gcd(a, b) > 1$.

Vậy chỉ cần biết từng số trong $[L, R]$ có phi chính phương hay không (kiểm tra $i^2 \mid x$ với $i \le \sqrt{x} \le 31623$) và tính $\gcd$ cho từng cặp. Em nhập $L$, $R$ rồi bấm Tiếp để xem bảng các cặp được tô màu theo từng lý do:

L R

Ví dụ nhanh:

Cách 1Vét cạn trên tích a × b – Nhóm 1

Làm đúng theo đề: với mỗi cặp $(a, b)$ tính $p = a \times b$ (tối đa $10^{18}$, vẫn vừa long long), rồi thử mọi $i$ từ 2 khi $i^2 \le p$ xem $i^2$ có chia hết $p$ không.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi cặp, tính p = a·b và thử mọi i² ≤ p.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Nếu $p$ có ước chính phương thì thường tìm thấy rất sớm ($i = 2$ hoặc $3$), nhưng khi $p$ phi chính phương thì vòng for phải chạy đủ $\sqrt{p} \approx R$ lần. Với $R = 10^4$ đã là khoảng $1{,}4 \cdot 10^5$ cặp × $10^4$ lần thử.

Không gian$O(1)$

Thời gian$O(m^2 R)$

Kết quả chạy thật: bản C++ đúng 14/100 test – ăn trọn Nhóm 1; sai 86 test, đầu tiên là test 11 (quá thời gian); test đúng chậm nhất chạy 1,00s. Bản Python đúng 10/100 test – ăn trọn Nhóm 1; sai mọi test từ test 11 trở đi (quá thời gian); test đúng chậm nhất chạy 0,02s.

Cách 2Dùng nhận xét số học, kiểm tra từng số – Nhóm 1, 2, 3

Áp dụng mấu chốt ở trên: không cần nhân $a \times b$ nữa, chỉ cần kiểm tra $a$, $b$ có phi chính phương không và $\gcd(a, b)$. Hàm squareFree(x) thử $i^2 \mid x$ với $i \le \sqrt{x}$ – chỉ tốn $\sqrt{x}$ thay vì $\sqrt{a b}$.

C++▶ Chạy tay từng dòng codeCách 2: a·b có ước chính phương ⇔ a hoặc b có, hoặc gcd(a, b) > 1 (gọi squareFree cho từng cặp).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phép || "ngắt mạch": nếu !squareFree(a) đã đúng thì không gọi squareFree(b) và __gcd nữa.
2. Nhưng squareFree(a) vẫn bị gọi lại cho mỗi $b$ – cùng một số bị kiểm tra tới cả nghìn lần! Với $R = 10^6$ đó là khoảng $5 \cdot 10^5$ cặp × $2 \cdot 10^3$ phép thử.

Không gian$O(1)$

Thời gian$O(m^2 \sqrt{R})$

Kết quả chạy thật: bản C++ đúng 60/100 test – ăn trọn Nhóm 1, Nhóm 2, Nhóm 3; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy 0,39s. Bản Python đúng 10/100 test – ăn trọn Nhóm 1; sai mọi test từ test 11 trở đi (quá thời gian); test đúng chậm nhất chạy 0,02s.

Cách 3Tính trước cho từng số – Full điểm

Sửa đúng chỗ lãng phí của cách 2: mỗi số trong $[L, R]$ chỉ kiểm tra phi chính phương một lần, lưu vào mảng sf. Sau đó duyệt cặp chỉ còn tra mảng và tính $\gcd$.

C++▶ Chạy tay từng dòng codeCách 3 (full điểm): tính trước sf cho từng số, rồi duyệt cặp.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sf[i] ứng với số $L + i$ (dời chỉ số về 0 vì $L$ có thể tới $10^9$).
2. Phần tính trước tốn $1001 \times 31623 \approx 3 \cdot 10^7$ phép chia, phần duyệt cặp $5 \cdot 10^5$ lần __gcd – rất nhanh.
3. Bản Python còn chậm ở vòng thử chia nên mình chỉ thử chia cho các số nguyên tố $p \le \sqrt{R}$ (sàng trước khoảng 3400 số nguyên tố) – đúng vì nếu $x$ có ước chính phương $k^2$ thì cũng có ước $p^2$ với $p$ nguyên tố.

Không gian$O(m)$

Thời gian$O(m\sqrt{R} + m^2 \log R)$

Kết quả chạy thật: bản C++ đúng 100/100 test – ăn trọn Nhóm 1, Nhóm 2, Nhóm 3, Nhóm 4, Nhóm 5; test đúng chậm nhất chạy 0,09s. Bản Python đúng 100/100 test – ăn trọn Nhóm 1, Nhóm 2, Nhóm 3, Nhóm 4, Nhóm 5; test đúng chậm nhất chạy 0,30s.

Tổng kếtKết quả chạy thật của các cách

Cách	Nhóm 1 test 1–10	Nhóm 2 test 11–30	Nhóm 3 test 31–60	Nhóm 4 test 61–80	Nhóm 5 test 81–100	Tổng	Chậm nhất (test đúng)
Cách 1 – C++	10/10	4/20 quá thời gian	0/30 quá thời gian	0/20 quá thời gian	0/20 quá thời gian	14/100	1,00s
Cách 1 – Python	10/10	0/20 quá thời gian	0/30 quá thời gian	0/20 quá thời gian	0/20 quá thời gian	10/100	0,02s
Cách 2 – C++	10/10	20/20	30/30	0/20 quá thời gian	0/20 quá thời gian	60/100	0,39s
Cách 2 – Python	10/10	0/20 quá thời gian	0/30 quá thời gian	0/20 quá thời gian	0/20 quá thời gian	10/100	0,02s
Cách 3 – C++	10/10	20/20	30/30	20/20	20/20	100/100	0,09s
Cách 3 – Python	10/10	20/20	30/30	20/20	20/20	100/100	0,30s

Ghi chú của mình: số liệu trên là chạy thật trên 100 test của CLUE OJ với giới hạn 1 giây; thời gian là thời gian CPU trên máy của mình (biên dịch g++ -O2). Cách 3 bản C++ đạt 100/100 test. Bài học rút ra: (1) biến đổi điều kiện trên tích $a \times b$ thành điều kiện trên từng số; (2) cái gì dùng lại nhiều lần thì tính trước một lần.

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 😇