Lễ hội trà

Nguồn: CLUE OJ – Chương 47: Các bài tập về số nguyên tố Độ khó: Trung bình Ước số Số nguyên tố Phân tích thừa số

Đề bài

Tỉnh TN chuẩn bị tổ chức Lễ hội văn hóa Trà. Ban tổ chức ước lượng sẽ có $N$ đại biểu đến tham dự và dự kiến mời các đại biểu đi tham quan các địa điểm du lịch nổi tiếng của tỉnh. Các đại biểu được chia thành các đoàn tham quan, số lượng người của mỗi đoàn phải bằng nhau (chia đều), số lượng này phải lớn hơn 1 và nhỏ hơn tổng số đại biểu.

Một phương án chia đoàn được gọi là Đẹp nếu số lượng người của mỗi đoàn không thể bị chia thành các đoàn nhỏ hơn và bằng nhau nữa. Với mỗi số lượng người cụ thể của các đoàn tham quan, ban tổ chức phải lên một kịch bản đón tiếp riêng, và với cách chia đoàn Đẹp thì ban tổ chức cũng có một kịch bản đón tiếp Đẹp.

Hãy giúp ban tổ chức tính số kịch bản đón tiếp cần phải chuẩn bị và trong đó có bao nhiêu kịch bản Đẹp.

Dữ liệu vào: dòng 1 chứa số nguyên $T$ là số bộ dữ liệu $(T \le 100)$. $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $N$ $(N \le 10^{12})$.

Kết quả: ghi ra $T$ dòng tương ứng, mỗi dòng chứa 2 số là số kịch bản cần chuẩn bị và số kịch bản Đẹp, cách nhau một dấu cách.

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

• $50\%$ số điểm có $T = 1$, $N \le 10^5$;
• $30\%$ số điểm có $T \le 10$, $N \le 10^9$;
• $20\%$ số điểm có $T \le 100$, $N \le 10^{12}$.

Ví dụ – input

2
8
4

Ví dụ – output

2 1
1 1

Giải thích ví dụ: $N = 8$: có 2 cách chia đoàn, mỗi đoàn $2$ người hoặc $4$ người; trong đó chia mỗi đoàn $2$ người là Đẹp (đoàn $4$ người còn chia được thành 2 đoàn $2$ người). $N = 4$: chỉ có 1 cách chia, mỗi đoàn $2$ người, và cách này cũng Đẹp.

Lời mở đầu

Đọc kỹ đề, mọi chuyện "đoàn tham quan" chỉ là vỏ bọc: số người mỗi đoàn $d$ phải chia hết $N$ và $1 < d < N$, tức $d$ là một ước thật sự của $N$. Đoàn $d$ người "không chia nhỏ đều được nữa" nghĩa là $d$ không có ước nào khác ngoài $1$ và chính nó – tức $d$ là số nguyên tố. Bài toán trở thành: đếm số ước thật sự của $N$ và số ước nguyên tố của $N$ (nhỏ hơn $N$). Với $N$ tới $10^{12}$, mình sẽ đi từ cách duyệt thẳng, tới cách duyệt cặp ước đến $\sqrt N$, rồi tới cách chuẩn: phân tích thừa số nguyên tố.

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, 3 mứcÝ tưởngước & ước nguyên tốCách 1duyệt O(N)Cách 2cặp ước tới √NCách 3phân tích thừa sốTổng kếtkết quả chạy thật

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

Bộ test có 100 test, chia đúng 3 mức như đề:

Test	T	N	Số bộ hỏi	Bộ có đáp án 0 0	Số kịch bản lớn nhất	Số kịch bản Đẹp lớn nhất
1–50	1	1 … 98.500	50	10	30	5
51–80	10	102.535 … 984.427.029	300	20	126	6
81–100	100	1.004.502.896 … 999.999.999.989	2.000	176	430	8

• Các bộ có đáp án 0 0 là khi $N$ nguyên tố (không có ước nào nằm giữa $1$ và $N$) – và có cả $N = 1$ ở test 1.
• Test 100 gồm toàn số nguyên tố sát $10^{12}$ (999.999.999.989, 999.999.999.961, …). Đây là trường hợp xấu nhất cho mọi cách "thử chia tới $\sqrt N$": phải thử đủ khoảng $10^6$ lần cho mỗi số.

Subtask	Điều kiện	Các test	Cách ăn được
1 (50%)	$T = 1$, $N \le 10^5$	1 – 50	Cách 1, 2, 3
2 (30%)	$T \le 10$, $N \le 10^9$	51 – 80	Cách 2, 3
3 (20%)	$T \le 100$, $N \le 10^{12}$	81 – 100	Cách 3 (cách 2 tuỳ)

Ý tưởngKịch bản = ước thật sự, kịch bản Đẹp = ước nguyên tố

Chia $N$ người thành các đoàn bằng nhau, mỗi đoàn $d$ người ⇔ $d \mid N$. Điều kiện $1 < d < N$ loại đi hai ước "tầm thường" là $1$ và $N$. Đoàn $d$ người còn chia đều được thành các đoàn nhỏ hơn (mỗi đoàn hơn 1 người) ⇔ $d$ có một ước $e$ với $1 < e < d$ ⇔ $d$ là hợp số. Vậy:

Đáp án

Số kịch bản $=$ số ước của $N$ trừ $2$ (bỏ $1$ và $N$)  ·  Số kịch bản Đẹp $=$ số ước nguyên tố của $N$ nhỏ hơn $N$.

Nếu phân tích $N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ thì mỗi ước của $N$ có dạng $p_1^{x_1} \cdots p_k^{x_k}$ với $0 \le x_i \le e_i$, nên:

Công thức

$$\text{số ước}(N) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1), \qquad \text{số ước nguyên tố} = k$$

Trường hợp đặc biệt: $N = 1$ hoặc $N$ nguyên tố thì không có cách chia nào, in 0 0 (với $N$ nguyên tố, công thức cho $k = 1$ nhưng ước nguyên tố duy nhất chính là $N$, không được tính). Ví dụ $N = 8 = 2^3$: số ước $= 4$, trừ 2 còn $2$; ước nguyên tố chỉ có $2$ → 2 1. Em nhập $N$ rồi bấm Tiếp để xem từng bước:

N =

Ví dụ nhanh:

Còn lại chỉ là: làm sao đếm nhanh với $N$ tới $10^{12}$ và tới $100$ bộ dữ liệu.

Cách 1Duyệt mọi d từ 2 tới N − 1

Làm thẳng theo định nghĩa: với mỗi $d$ từ $2$ tới $N - 1$, nếu $N \bmod d = 0$ thì tăng số kịch bản; nếu thêm $d$ là số nguyên tố (kiểm tra bằng thử chia tới $\sqrt d$) thì tăng số kịch bản Đẹp.

C++▶ Chạy tay từng dòng codeCách 1: duyệt d = 2 … N − 1, gặp ước thì kiểm tra nguyên tố bằng thử chia.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng ngoài chạy $N - 2$ lần; hàm isPrime chỉ được gọi với các ước (rất ít), nên tổng thời gian khoảng $O(N)$ mỗi bộ.
• Với $N \le 10^5$ thì chạy tức thì. Với $N$ cỡ $10^9$ là $10^9$ phép chia lấy dư – quá chậm; $10^{12}$ thì không thể.

Không gian$O(1)$

Thời gian$O(T \cdot N)$

Kết quả chạy thật: bản C++ đúng 53/100 test (Subtask 1: 50/50, Subtask 2: 3/30, Subtask 3: 0/20), test đúng chạy lâu nhất 1,374 giây; 47 test quá thời gian; bản Python đúng 50/100 test (Subtask 1: 50/50, Subtask 2: 0/30, Subtask 3: 0/20), test đúng chạy lâu nhất 0,054 giây; 50 test quá thời gian.

Cách 2Duyệt cặp ước (d, N/d) với d·d ≤ N

Ước của $N$ đi theo cặp: nếu $d \mid N$ thì $N/d$ cũng là ước, và trong mỗi cặp có một số $\le \sqrt N$. Chỉ cần duyệt $d$ tới $\sqrt N$ (khoảng $10^6$ với $N = 10^{12}$), gặp ước $d$ thì xét cả $d$ và $N/d$ (cẩn thận khi $d = N/d$, và bỏ $1$, $N$). Mỗi ước vẫn kiểm tra nguyên tố bằng thử chia.

C++▶ Chạy tay từng dòng codeCách 2: duyệt d tới √N, mỗi ước d kéo theo ước N/d; kiểm tra nguyên tố từng ước.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng chính chỉ chạy $\sqrt N$ lần: $10^6$ lần với $N = 10^{12}$. Với $T = 100$ là $10^8$ phép chia long long – C++ chạy khoảng 1 giây, Python thì không kịp.
• Mỗi ước còn phải kiểm tra nguyên tố. Ước nhỏ kiểm tra rất nhanh, nhưng ước lớn (như $N/2$) mà là số nguyên tố thì isPrime tốn thêm tới $\sqrt{N/2}$ bước.

Không gian$O(1)$

Thời gian$O\big(T(\sqrt N + \text{ước} \cdot \sqrt N)\big)$ trong trường hợp xấu

Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 50/50, Subtask 2: 30/30, Subtask 3: 20/20), test đúng chạy lâu nhất 0,919 giây; bản Python đúng 80/100 test (Subtask 1: 50/50, Subtask 2: 30/30, Subtask 3: 0/20), test đúng chạy lâu nhất 0,053 giây; 20 test quá thời gian.

Cách 3Phân tích thừa số nguyên tố + công thức đếm ước

Dùng công thức ở phần Ý tưởng: thử chia $p = 2, 3, \ldots$ khi $p^2 \le x$, chia hết bao nhiêu lần thì được số mũ $e$, nhân dồn $(e + 1)$ vào số ước và đếm số thừa số $k$. Phần $x > 1$ còn lại cuối cùng chắc chắn là một số nguyên tố. Không cần kiểm tra nguyên tố riêng cho từng ước nữa. Điểm mạnh: mỗi lần chia hết, $x$ giảm hẳn, nên vòng lặp thường dừng sớm hơn nhiều so với $\sqrt N$.

C++▶ Chạy tay từng dòng codeCách 3: phân tích N ra thừa số nguyên tố, số ước = tích (e + 1), số ước nguyên tố = số thừa số khác nhau.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Trường hợp xấu nhất là $N$ nguyên tố sát $10^{12}$ (như test 100): vòng thử chạy đủ $10^6$ lần, $T = 100$ bộ là $10^8$ phép chia – C++ vẫn chạy kịp trong 2 giây.
• Bản Python chạy $10^8$ phép chia là quá chậm, nên mình sàng sẵn các số nguyên tố tới $10^6$ (78.498 số) và chỉ thử chia cho số nguyên tố: số phép chia giảm khoảng 13 lần.
• Nhớ hai trường hợp đặc biệt: $N = 1$ và $N$ nguyên tố đều in 0 0.

Không gian$O(1)$ (Python: $O(\sqrt{N_{\max}})$ cho mảng sàng)

Thời gian$O(T\sqrt N)$, thường nhanh hơn nhiều

Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 50/50, Subtask 2: 30/30, Subtask 3: 20/20), test đúng chạy lâu nhất 1,016 giây; bản Python đúng 100/100 test (Subtask 1: 50/50, Subtask 2: 30/30, Subtask 3: 20/20), test đúng chạy lâu nhất 1,819 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ộ 100 test với giới hạn 2 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–50	Subtask 2 test 51–80	Subtask 3 test 81–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	50/50	3/30	0/20	53/100	1,374s
Cách 1 – Python	50/50	0/30	0/20	50/100	0,054s
Cách 2 – C++	50/50	30/30	20/20	100/100	0,919s
Cách 2 – Python	50/50	30/30	0/20	80/100	0,053s
Cách 3 – C++	50/50	30/30	20/20	100/100	1,016s
Cách 3 – Python	50/50	30/30	20/20	100/100	1,819s

Ghi chú của mình: cả 3 cách đều cho đáp án đúng ở mọi test chạy kịp. Cách 1 chỉ ăn chắc subtask 1. Bản C++ của cách 2 vẫn qua hết vì $10^8$ phép chia vừa lọt 2 giây, nhưng bản Python của cách 2 thì mất trọn subtask 3. Cách 3 (phân tích thừa số) là lời giải chuẩn, không phải kiểm tra nguyên tố riêng từng ước. Với Python, test 100 (100 số nguyên tố sát $10^{12}$) chạy khoảng 1,8 – 1,9 giây – sát giới hạn, nhờ chỉ thử chia cho các số nguyên tố đã sàng sẵn. Bài học: "không chia nhỏ đều được nữa" chính là "số nguyên tố", và đếm ước nên đi qua phân tích thừa số.

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 😇