Bài tập về nhà

Nguồn: Đề thi Tin học trẻ bảng B huyện đoàn Kim Sơn 2023 – 2024 (Bài 4) Độ khó: Trung bình Ước số Số chính phương Sàng nguyên tố

Đề bài

Trong buổi học Toán tiếp theo, Thầy lại cho ôn tập về số học, trong đó có các khái niệm: ước số, số chính phương, số nguyên tố, … và cho bài tập về nhà cho cả lớp tự luyện tập.

Khái niệm:

• Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương (lũy thừa bậc 2) của một số nguyên.
• Số nguyên $b$ $(b \ne 0)$ gọi là ước số của số nguyên $a$ nếu $a$ chia hết cho $b$.
• Số nguyên tố là số tự nhiên chỉ có 2 ước số, gồm 1 và chính nó.

Yêu cầu: Thầy cho dãy số $A$ có $n$ phần tử $a_1, a_2, \ldots, a_n$ và hỏi có bao nhiêu số có đúng 3 ước số dương trong dãy số $A$.

Dữ liệu vào: dòng 1 chứa duy nhất số nguyên dương $n$ $(1 \le n \le 10^6)$. Dòng 2 gồm $n$ số nguyên dương $a_i$ $(0 < a_i \le 10^9)$, giữa các số cách nhau bởi một dấu cách.

Kết quả: ghi ra số lượng số có đúng 3 ước số dương. Nếu không có số nào thỏa mãn thì ghi $0$.

Ràng buộc: có $60\%$ điểm ứng với $1 \le n \le 10^3$; $40\%$ điểm ứng với $1 \le n \le 10^6$.

Giới hạn: thời gian 1 giây. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

4
3 9 8 81

Ví dụ 1 – output

1

Ví dụ 2 – input

3
10 7 100

Ví dụ 2 – output

0

Giải thích ví dụ: ví dụ 1 có $n = 4$, chỉ có phần tử $a_2 = 9$ có 3 ước là $1, 3, 9$ ($81$ có tới 5 ước $1, 3, 9, 27, 81$). Ví dụ 2 không có số nào.

Lưu ý: trên CLUE OJ bài này chỉ được nộp 1 lần duy nhất, điểm chấm thế nào là thế đó – nên kiểm tra thật kỹ trước khi nộp.

Lời mở đầu

Đếm ước của từng số bằng cách duyệt tới căn là cách đầu tiên ai cũng nghĩ tới, nhưng với $10^6$ số và mỗi số tới $10^9$ thì không thể chạy kịp. Nhận xét then chốt: số có đúng 3 ước là số rất "đặc biệt" – nó là bình phương của một số nguyên tố. Khi đó mỗi số chỉ cần một phép lấy căn và một lần tra mảng sàng.

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ộ test100 test, 2 mứcÝ tưởng3 ước ⇔ p²Cách 1đếm ước tới √aCách 2căn + sàngTổng kếtkết quả chạy thật

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

Test	n	Giá trị $a_i$	Số chính phương trong dãy	Đáp án
1 – 60	3 – 1.000	1 … 100.032.762	0 – 7	0 – 2
61 – 100	10.000 – 1.000.000	2 … 100.032.767	16 – 2.492	1 – 498

• Giá trị lớn nhất trong bộ test khoảng $10^8$ (đề cho tới $10^9$). Các số chính phương được rải xen vào dãy, phần lớn còn lại là số "ngẫu nhiên".
• Có số $1$ trong dãy: $1$ là số chính phương nhưng chỉ có 1 ước, và $\sqrt 1 = 1$ không phải số nguyên tố.

Subtask	Điều kiện	Các test	Cách ăn được
1 (60%)	$n \le 10^3$	1 – 60	Cách 1, 2
2 (40%)	$n \le 10^6$	61 – 100	Cách 2

Ý tưởngCó đúng 3 ước ⇔ là bình phương của một số nguyên tố

Ước của $x$ đi theo cặp $(d, x/d)$. Nếu $x$ không là số chính phương thì không có $d = x/d$, số ước luôn là số chẵn – không thể bằng 3. Vậy $x = s^2$ và các ước của $x$ gồm cặp $(d, x/d)$ với $d < s$ cộng thêm ước $s$ đứng một mình.

Số ước bằng 3 ⇔ chỉ có đúng một cặp $(1, x)$ và ước $s$ ⇔ $s$ không có ước nào ngoài $1$ và chính nó ⇔ $s$ là số nguyên tố:

Kết luận

$$x \text{ có đúng 3 ước} \iff x = p^2 \text{ với } p \text{ nguyên tố} \quad (\text{ước là } 1,\ p,\ p^2)$$

Với $x \le 10^9$ thì $p \le \sqrt{10^9} < 31\,623$: chỉ cần sàng Eratosthenes tới $31\,623$.

Em nhập dãy số rồi bấm Tiếp để xem từng số được kiểm tra:

Dãy a:

Ví dụ nhanh:

Cách 1Đếm số ước của từng số, duyệt tới √a

Với mỗi $x$, duyệt $d$ từ $1$ khi $d^2 \le x$; gặp $d \mid x$ thì cộng 1 cho $d$ và cộng thêm 1 cho $x/d$ nếu $x/d \ne d$. Đếm các $x$ có đúng 3 ước.

C++▶ Chạy tay từng dòng codeCách 1: mỗi x đếm ước theo cặp (d, x/d) với d·d ≤ x, đếm các x có đúng 3 ước.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi số tốn $\sqrt{a_i}$ bước, tới $10^4$ với $a_i \approx 10^8$. $n = 10^3$ → $10^7$ bước: chạy kịp. $n = 10^6$ → $10^{10}$ bước: không thể.

Không gian$O(1)$

Thời gian$O(n\sqrt{a})$

Kết quả chạy thật: bản C++ đúng 70/100 test (Subtask 1: 60/60, Subtask 2: 10/40), test đúng chạy lâu nhất 0,289 giây; 30 test quá thời gian; bản Python đúng 60/100 test (Subtask 1: 60/60, Subtask 2: 0/40), test đúng chạy lâu nhất 0,670 giây; 40 test quá thời gian.

Cách 2Lấy căn bậc hai + tra sàng – Full điểm

Sàng Eratosthenes tới $31\,623$ một lần. Với mỗi $x$, tính $s = \lfloor \sqrt x \rfloor$ rồi kiểm tra $s \cdot s = x$ và $s$ nguyên tố. Hàm sqrtl trả số thực nên có thể lệch $1$ đơn vị với số lớn; hai vòng while chỉnh lại cho chắc. Python có sẵn math.isqrt tính căn nguyên chính xác.

C++▶ Chạy tay từng dòng codeCách 2: sàng tới 31623; mỗi x lấy s = ⌊√x⌋, đếm nếu s·s = x và s nguyên tố.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi số chỉ tốn $O(1)$: một lần lấy căn, vài phép nhân, một lần tra mảng. Phần nặng nhất là đọc $10^6$ số – nhớ ios::sync_with_stdio(0); cin.tie(0); (C++) và sys.stdin.buffer.read() (Python).

Không gian$O(\sqrt{a_{\max}})$

Thời gian$O(\sqrt{a_{\max}} \log\log + n)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 60/60, Subtask 2: 40/40), test đúng chạy lâu nhất 0,131 giây; bản Python đúng 100/100 test (Subtask 1: 60/60, Subtask 2: 40/40), test đúng chạy lâu nhất 0,694 giây.

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

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

Lời giải	Subtask 1 test 1–60	Subtask 2 test 61–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	60/60	10/40	70/100	0,289s
Cách 1 – Python	60/60	0/40	60/100	0,670s
Cách 2 – C++	60/60	40/40	100/100	0,131s
Cách 2 – Python	60/60	40/40	100/100	0,694s

Ghi chú của mình: cả 2 cách đều cho đáp án đúng ở mọi test chạy kịp. Cách 1 ăn trọn 60% (subtask 1) và lọt thêm 10 test nhỏ của subtask 2 ở bản C++. Cách 2 dựa trên nhận xét "có đúng 3 ước ⇔ bình phương của số nguyên tố", mỗi số chỉ tốn $O(1)$; phần tốn thời gian nhất lúc này là đọc $10^6$ số (Python 0,69 giây). Vì bài chỉ được nộp 1 lần, nên chọn ngay cách 2.

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 😇