Đếm ước (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B, C1, C2)
Đề bài
Với một số nguyên dương $n$, Alice đặc biệt chú ý tới những ước nguyên dương của $n^2$ thoả mãn đồng thời hai điều kiện: nhỏ hơn $n$ và không phải là ước của $n$.
Yêu cầu: cho số nguyên dương $m$, đặt $n = m \times (m + 1) \times (m + 2)$. Hãy đếm số ước nguyên dương của $n^2$ nhỏ hơn $n$ và không là ước của $n$.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên $T$ – số bộ dữ liệu.
- $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $m$.
Kết quả: gồm $T$ dòng, dòng thứ $i$ là đáp án của bộ dữ liệu thứ $i$.
Subtask:
- Subtask 1 (25% số điểm): $m \le 10^3$, $T \le 10$.
- Subtask 2 (25% số điểm): $m \le 10^6$, $T \le 10$.
- Subtask 3 (25% số điểm): $m \le 10^6$, $T \le 10^3$.
- Subtask 4 (25% số điểm): $m \le 10^6$, $T \le 10^5$.
Giới hạn thời gian: 0,2 giây (rất chặt). Dữ liệu nhập từ bàn phím và in ra màn hình.
2
1
21
3Giải thích:
- $m = 1$: $n = 6$, $n^2 = 36$. Các ước của 36 nhỏ hơn 6 là $1, 2, 3, 4$; chỉ có $4$ không là ước của 6 → đáp án 1.
- $m = 2$: $n = 24$, $n^2 = 576$. Các ước của 576 nhỏ hơn 24 mà không là ước của 24 là $9, 16, 18$ → đáp án 3.
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B, C1, C2 (bài DIV). Đề được mình viết lại cho dễ đọc; phần giải thích ví dụ là mình tự thêm.
Lời mở đầu
Bài này là một bài số học "chuẩn mực": vét cạn thì dễ nhưng chậm khủng khiếp ($n$ có thể tới $10^{18}$), còn lời giải đẹp chỉ cần một nhận xét ghép cặp và công thức số ước. Phần còn lại là cuộc đua tốc độ: giới hạn thời gian chỉ 0,2 giây cho $10^5$ truy vấn, nên phải biết dùng sàng ước nguyên tố nhỏ nhất. Mình đi lần lượt 3 cách, mỗi cách ăn thêm một subtask.
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 có gì?
Bộ test của mình gồm 20 test, chia đều 5 test cho mỗi subtask đúng tỉ lệ 25% của đề. Test 1 là ví dụ của đề. Lời giải cuối cùng (cách 3, bản đọc nhanh) đã được nộp thử trên hệ thống chấm chính thức tinhoctre.vn và đạt 100/100 điểm.
| Nhóm | Test | $T$ lớn nhất | $m$ nhỏ nhất – lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|
| Subtask 1 | 1–5 | 10 | 1 – 1.000 | 12.868 |
| Subtask 2 | 6–10 | 10 | 1 – 1.000.000 | 807.734 |
| Subtask 3 | 11–15 | 1.000 | 1 – 1.000.000 | 2.842.790 |
| Subtask 4 | 16–20 | 100.000 | 1 – 1.000.000 | 3.075.497 |
- Test 19 có $10^5$ truy vấn đều là $m = 10^6$ (khó nhất cho cách thử chia vì $m, m+1, m+2$ đều lớn). Các test khác có $m$ ngẫu nhiên, $m$ sát $10^6$, $m$ có nhiều ước (như 720, 840, 554400...).
- Đáp án lớn nhất khoảng $3 \cdot 10^6$ – vừa
int, nhưng $n$ thì tới khoảng $10^{18}$ nên phải dùnglong longkhi tính $n$.
Kết quả chạy thật (giới hạn 0,2 giây, đo thời gian CPU) của các cách theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 thử chia | Cách 2 Python | Cách 3 sàng | Cách 3 Python |
|---|---|---|---|---|---|---|---|
| Subtask 1 (25%) | $m \le 10^3$, $T \le 10$ | 1–5 | 2/5 | 5/5 | 5/5 | 5/5 | 5/5 |
| Subtask 2 (25%) | $m \le 10^6$, $T \le 10$ | 6–10 | 0/5 | 5/5 | 5/5 | 5/5 | 0/5 |
| Subtask 3 (25%) | $m \le 10^6$, $T \le 10^3$ | 11–15 | 0/5 | 5/5 | 5/5 | 5/5 | 1/5 |
| Subtask 4 (25%) | $m \le 10^6$, $T \le 10^5$ | 16–20 | 0/5 | 1/5 | 0/5 | 5/5 | 0/5 |
Ý tưởngGhép cặp các ước của n²
Nhận xét 1 – ghép cặp. Nếu $d$ là ước của $n^2$ thì $\dfrac{n^2}{d}$ cũng là ước của $n^2$, và:
- $d < n \iff \dfrac{n^2}{d} > n$. Vậy các ước nhỏ hơn $n$ và các ước lớn hơn $n$ ghép thành từng cặp, số lượng bằng nhau.
- Riêng $d = n$ ghép với chính nó.
Gọi $\tau(x)$ là số ước dương của $x$. Suy ra: số ước của $n^2$ nhỏ hơn $n$ là $\dfrac{\tau(n^2) - 1}{2}$.
Nhận xét 2 – trừ đi các ước của $n$. Mọi ước của $n$ đều là ước của $n^2$. Các ước của $n$ nhỏ hơn $n$ có $\tau(n) - 1$ số (bỏ chính $n$). Vậy:
Nhận xét 3 – công thức số ước. Nếu $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ thì $n^2 = p_1^{2e_1} \cdots p_k^{2e_k}$, nên
$$\tau(n) = \prod (e_i + 1), \qquad \tau(n^2) = \prod (2e_i + 1).$$
Và ta không cần phân tích số $n$ khổng lồ: chỉ cần phân tích riêng $m$, $m + 1$, $m + 2$ (mỗi số $\le 10^6 + 2$) rồi cộng dồn số mũ của cùng một số nguyên tố. Thử với $m = 2$: $n = 2 \cdot 3 \cdot 4 = 2^3 \cdot 3^1$, $\tau(n) = 4 \cdot 2 = 8$, $\tau(n^2) = 7 \cdot 3 = 21$, đáp án $= 10 - 7 = 3$. Đúng!
Em nhập $m$ (nhỏ) rồi bấm Tiếp để xem các ước của $n^2$ được ghép cặp và đếm thế nào:
Cách 1Vét cạn theo định nghĩa
Duyệt mọi $d$ từ 1 tới $n - 1$, đếm các $d$ chia hết $n^2$ nhưng không chia hết $n$. Code ngắn, chắc chắn đúng – rất nên viết để kiểm tra các cách sau.
Kết quả chạy thật: Bản C++ đúng 2/20 test, quá thời gian test 3–20, chạy lâu nhất 1.003s. Bản Python đúng 2/20 test, quá thời gian test 3–20, chạy lâu nhất 1.072s. Chỉ 2 test có $m \le 10$ là kịp; với $m = 1000$ thì $n \approx 10^9$, mỗi truy vấn đã là $10^9$ phép chia – quá chậm ngay từ subtask 1.
Cách 2Công thức + phân tích bằng thử chia
Dùng công thức ở phần ý tưởng. Để phân tích $x$ ra thừa số nguyên tố, ta thử chia $x$ cho $p = 2, 3, 4, \ldots$ khi $p^2 \le x$; mỗi lần chia hết thì tăng số mũ của $p$. Phần còn lại $> 1$ (nếu có) là một số nguyên tố. Số mũ được cộng dồn vào map f cho cả ba số $m, m+1, m+2$.
- Không cần kiểm tra $p$ có nguyên tố không: khi tới $p$ hợp số thì các ước nguyên tố nhỏ hơn của nó đã bị chia hết khỏi $x$, nên $x$ không thể chia hết cho $p$.
- Vì $m, m+1, m+2$ đôi một chỉ có thể chung ước nguyên tố 2 (giữa $m$ và $m+2$), nên việc "cộng dồn" thật ra chỉ xảy ra với $p = 2$ – nhưng dùng
mapthì không cần nghĩ tới chuyện đó.
Kết quả chạy thật: Bản C++ đúng 16/20 test, quá thời gian test 16–19, chạy lâu nhất 0.333s. Bản Python đúng 15/20 test, quá thời gian test 16–20, chạy lâu nhất 1.008s. Mỗi truy vấn tốn khoảng $3 \cdot \sqrt{10^6} = 3000$ phép chia; với $T = 10^3$ là $3 \cdot 10^6$ phép – nhẹ nhàng, nhưng với $T = 10^5$ là $3 \cdot 10^8$ phép chia, vượt xa 0,2 giây → mất subtask 4.
Cách 3Sàng ước nguyên tố nhỏ nhất (full điểm)
Thay vì thử chia, ta sàng trước mảng spf[x] = ước nguyên tố nhỏ nhất của $x$, với mọi $x \le 10^6 + 2$. Khi đó phân tích $x$ cực nhanh: lấy $p = \text{spf}[x]$, chia $x$ cho $p$ tới khi hết, lặp lại với phần còn lại. Mỗi số $x \le 10^6$ có không quá 19 thừa số nguyên tố (tính cả lặp), nên mỗi truy vấn chỉ vài chục phép tính.
- Sàng: với mỗi $i$ chưa có
spf(tức $i$ nguyên tố), duyệt các bội $j$ của $i$ và gánspf[j] = inếu chưa gán. Tổng số bước khoảng $N \log \log N$. - Thay
mapbằngvectorcác cặp (p, e) – $n$ chỉ có khoảng chục ước nguyên tố khác nhau nên tìm tuyến tính còn nhanh hơn map. - Dùng
scanf/printfcho nhanh. Bản mình nộp lên tinhoctre.vn còn đọc bằngfreadvà dùng sàng tuyến tính, nhưng bản trên đã chạy dưới 0,06 giây CPU trên test lớn nhất.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.060s – full điểm. Bản Python đúng 6/20 test, quá thời gian test 6–13, 15–20, chạy lâu nhất 0.638s: riêng việc sàng $10^6$ phần tử bằng vòng lặp Python đã tốn khoảng 0,5 giây, vượt giới hạn 0,2 giây – với giới hạn này Python chỉ ăn được những test có $m$ nhỏ. Bạn nào thi bằng Python thì cách 2 (thử chia) lại có lợi hơn ở subtask 1–3.
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 mọi d | C++ | 2/20 | 1.003s | 0 điểm (tính theo subtask) |
| 1. Vét cạn mọi d | Python | 2/20 | 1.072s | 0 điểm (tính theo subtask) |
| 2. Công thức + thử chia | C++ | 16/20 | 0.333s | 75 điểm (tính theo subtask) |
| 2. Công thức + thử chia | Python | 15/20 | 1.008s | 75 điểm (tính theo subtask) |
| 3. Công thức + sàng | C++ | 20/20 | 0.060s | 100 điểm (tính theo subtask) |
| 3. Công thức + sàng | Python | 6/20 | 0.638s | 25 điểm (tính theo subtask) |