Số học

Nguồn: CLUE OJ – KSCL HSG Thanh Hóa 2024–2025 Độ khó: Dễ Phân tích thừa số map

Đề bài

Bài 1 (6.0 điểm): Số học (Kỳ thi KSCL học sinh giỏi tỉnh lớp 12 lần 1, Thanh Hóa, năm học 2024–2025)

Cho số nguyên dương $N$. Em hãy thực hiện các yêu cầu sau:

• Đếm các ước nguyên dương của $N$;
• Tìm số nguyên tố lớn nhất là ước của $N$.

Dữ liệu vào: gồm một số nguyên dương $N$ $(1 < N \le 10^{12})$.

Kết quả:

• Dòng 1 ghi ra số lượng các ước nguyên dương của $N$;
• Dòng 2 ghi ra số nguyên tố lớn nhất là ước của $N$.

Giới hạn:

• Subtask 1: có 50% test tương ứng 3.0 điểm với $N \le 10^3$;
• Subtask 2: có 25% test tương ứng 1.5 điểm với $10^3 < N \le 10^6$;
• Subtask 3: có 25% test tương ứng 1.5 điểm với $10^6 < N \le 10^{12}$.

Giải thích ví dụ: $10$ có 4 ước là $1, 2, 5, 10$; ước nguyên tố lớn nhất là $5$. $13$ là số nguyên tố nên có 2 ước $1, 13$ và ước nguyên tố lớn nhất là chính nó.

Ví dụ 1 – input

10

Ví dụ 1 – output

4
5

Ví dụ 2 – input

13

Ví dụ 2 – output

2
13

Lời mở đầu

Bài mở màn của đề thi, hai yêu cầu nghe quen thuộc nhưng $N$ tới $10^{12}$ nên không thể "thử hết" được. Chìa khoá là phân tích $N$ ra thừa số nguyên tố: từ một lần phân tích ta trả lời được cả hai câu hỏi. Mình lưu kết quả phân tích vào một map (số nguyên tố → số mũ), vừa gọn vừa tự sắp xếp, lấy ước nguyên tố lớn nhất chỉ bằng một dòng.

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

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

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

Bộ test24 testÝ tưởngphân tích thừa sốCách 1O(N)Cách 2O(√N) + map

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

Bộ test có 24 test, chia đúng tỉ lệ 12 / 6 / 6 theo 3 subtask:

Subtask	Test	Các giá trị N	Số nguyên tố	Số ước lớn nhất
Subtask 1 $N \le 10^3$	1–12	10, 13, 174, 99, 101, 559, 852, 852, 895, 878, 995, 1.000	2 test	16
Subtask 2 $10^3 < N \le 10^6$	13–18	89.956, 889.958, 989.950, 999.958, 999.999, 999.997	0 test	64
Subtask 3 $10^6 < N \le 10^{12}$	19–24	1.000.000.007, 999.889.935, 8.999.889.985, 98.999.999.905, 999.999.999.962, 1.000.000.000.000	1 test	169

Riêng subtask 3, phân tích của các $N$ lớn như sau – có cả $N = 10^9 + 7$ là số nguyên tố, và test 23 có ước nguyên tố lớn nhất tới hơn $10^{10}$ (vượt int):

Test	N	Phân tích	Số ước	Ước nguyên tố lớn nhất
19	1.000.000.007	$1000000007$	2	1.000.000.007
20	999.889.935	$3 \cdot 5 \cdot 11 \cdot 17 \cdot 356467$	32	356.467
21	8.999.889.985	$5 \cdot 53 \cdot 179 \cdot 337 \cdot 563$	32	563
22	98.999.999.905	$5 \cdot 2741 \cdot 7223641$	8	7.223.641
23	999.999.999.962	$2 \cdot 37 \cdot 13513513513$	8	13.513.513.513
24	1.000.000.000.000	$2^{12} \cdot 5^{12}$	169	5

Đối chiếu subtask với test thật và số test đúng của từng cách (test 7 và 8 giống hệt nhau, đều là $N = 852$):

Subtask	Đề ghi	Test	Cách 1 $O(N)$	Cách 2 $O(\sqrt N)$ + map
Subtask 1	$N \le 10^3$	1–12	12/12	12/12
Subtask 2	$10^3 < N \le 10^6$	13–18	6/6	6/6
Subtask 3	$10^6 < N \le 10^{12}$	19–24	0/6	6/6

Ý tưởngPhân tích một lần, trả lời hai câu

Nếu $N = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ thì mỗi ước của $N$ có dạng $p_1^{f_1} \cdots p_k^{f_k}$ với $0 \le f_i \le e_i$ – mỗi $f_i$ có $e_i + 1$ cách chọn, nên:

Hai công thức

• Số ước của $N$ = $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$. Ví dụ $10^{12} = 2^{12} \cdot 5^{12}$ có $13 \cdot 13 = 169$ ước.
• Ước nguyên tố lớn nhất = $p_k$, thừa số nguyên tố lớn nhất.

Phân tích bằng cách chia thử $d = 2, 3, 4, \ldots$: chia $x$ cho $d$ tới khi không chia hết nữa. Chỉ cần thử tới khi $d \cdot d > x$: lúc đó nếu $x > 1$ thì $x$ là một số nguyên tố (vì nếu $x$ là hợp số thì nó phải có ước $\le \sqrt x$, mà các ước nhỏ đã bị chia hết rồi). Vì vậy chỉ mất tối đa $\sqrt{10^{12}} = 10^6$ bước.

Em nhập $N$ rồi bấm Tiếp để xem từng bước chia thử:

N =

Ví dụ nhanh:

Cách 1Thử mọi số tới N – Subtask 1, 2

Cách tự nhiên nhất: đếm ước bằng cách thử mọi $d$ từ 1 đến $N$; tìm ước nguyên tố lớn nhất bằng cách chia $x$ cho $d = 2, 3, \ldots$ cho tới khi $x = 1$ – thừa số chia được cuối cùng là lớn nhất (không cần kiểm tra nguyên tố, vì khi chia tới $d$ thì mọi ước nhỏ hơn đã bị chia hết, nên $d$ chia hết $x$ thì $d$ phải là số nguyên tố).

C++▶ Chạy tay từng dòng codeCách 1: thử mọi d từ 1 tới N để đếm ước; chia dần x cho d để tìm thừa số lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 18/24 test (quá thời gian ở test 19–24), test đúng chạy lâu nhất 0.01s; bản Python đúng 18/24 test (quá thời gian ở test 19–24), test đúng lâu nhất 0.15s. Ăn trọn subtask 1 và 2 ($N \le 10^6$), còn $N$ từ $10^9$ trở lên thì vòng lặp $10^9$–$10^{12}$ lần là quá chậm.

Cách 2Phân tích tới căn N, lưu vào map – Full điểm

C++▶ Chạy tay từng dòng codeCách 2: chia thử tới căn x, lưu thừa số vào map, số ước = tích (e + 1).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. d * d <= x: $x$ giảm dần khi bị chia, nên điều kiện dừng càng lúc càng sớm. $d$ phải là long long để d * d không tràn.
2. if (x > 1) mu[x]++;: phần còn lại là số nguyên tố lớn hơn $\sqrt{\cdot}$ – đừng quên dòng này (ví dụ $N = 10^9 + 7$ hay $N = 74 \cdot 13513513513$).
3. for (auto [p, e] : mu): duyệt từng cặp (thừa số, số mũ) để nhân $(e + 1)$.
4. mu.rbegin()->first: map sắp khoá tăng dần, phần tử cuối là khoá lớn nhất – chính là ước nguyên tố lớn nhất.

Không gian$O(\log N)$

Thời gian$O(\sqrt N)$

Kết quả chạy thật: bản C++ đúng 24/24 test, test đúng chạy lâu nhất 0.00s; bản Python đúng 24/24 test, test đúng lâu nhất 0.05s.

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

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Thử mọi số tới $N$	C++	18/24	0.01s	Quá thời gian test 19–24
	Python	18/24	0.15s	Quá thời gian test 19–24
2. Phân tích tới $\sqrt N$ + map	C++	24/24	0.00s	Full điểm
	Python	24/24	0.05s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Phân tích thừa số tới $\sqrt N$ là kỹ thuật nền tảng, nhớ 2 chi tiết: dùng long long và xử lý phần dư $x > 1$ sau vòng lặp.

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 😇