Ba số nguyên tố

Nguồn: CLUE OJ – Chương 47: Các bài tập về số nguyên tố Độ khó: Khá Sàng nguyên tố Số ước

Đề bài

Cho 2 số nguyên $n$ và $k$. Tìm số nguyên $m$ lớn nhất thỏa mãn các điều kiện sau:

• $m \le n$;
• Trong phân tích thừa số nguyên tố của $m$ có đúng ba số nguyên tố liên tiếp. Cụ thể, $m = p_1^{t_1} \times p_2^{t_2} \times p_3^{t_3}$, với $p_1, p_2, p_3$ là ba số nguyên tố liên tiếp và $t_1, t_2, t_3 \ge 1$;
• Số lượng các ước của $m$ đúng bằng $k$.

Yêu cầu: bạn hãy tìm số nguyên $m$ thỏa mãn yêu cầu đề bài. Dữ liệu vào đảm bảo luôn tồn tại kết quả.

Dữ liệu: vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên $n$ và $k$ $(1 \le n \le 10^{18};\ 8 \le k \le 2700)$.

Kết quả: ghi ra thiết bị ra chuẩn một số nguyên $m$ là kết quả của bài toán.

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

Ràng buộc:

• Subtask 1 ($20\%$ số điểm): $n \le 10^6$;
• Subtask 2 ($30\%$ số điểm): $k \le 24$;
• Subtask 3 ($30\%$ số điểm): $k \le 400$;
• Subtask 4 ($20\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ 1 – input

32 8

Ví dụ 1 – output

30

Ví dụ 2 – input

110 8

Ví dụ 2 – output

105

Giải thích ví dụ: $30 = 2 \cdot 3 \cdot 5$ có $(1+1)(1+1)(1+1) = 8$ ước và $2, 3, 5$ là ba số nguyên tố liên tiếp; $31, 32$ không thỏa. Với $n = 110$: $105 = 3 \cdot 5 \cdot 7$ có $8$ ước; các số $106, \ldots, 110$ không thỏa (ví dụ $110 = 2 \cdot 5 \cdot 11$ nhưng $2, 5, 11$ không liên tiếp).

Lời mở đầu

$n$ tới $10^{18}$ nên không thể duyệt từng $m$. Mấu chốt là công thức số ước: $m = p_1^{t_1} p_2^{t_2} p_3^{t_3}$ có đúng $(t_1+1)(t_2+1)(t_3+1)$ ước. Vậy thay vì tìm $m$, ta "đoán" bộ số mũ từ cách tách $k$ thành tích 3 thừa số, rồi đoán bộ ba nguyên tố liên tiếp. Mình đi từ cách duyệt $m$ giảm dần (ăn subtask 1) tới cách duyệt bộ số mũ × bộ ba nguyên tố chạy tức thì.

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, 4 subtaskÝ tưởngtách k thành 3 thừa sốCách 1duyệt m giảm dầnCách 2số mũ × bộ ba nguyên tốTổng kếtkết quả chạy thật

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

Test	n	k	Đáp án m
1–20	81 – 906.608	12 – 108	60 – 311.040
21–50	$\approx 1{,}6 \cdot 10^7$ – $\approx 9{,}3 \cdot 10^{11}$	8 – 24	10.938.133 – 862.775.087.701
51–80	$\approx 1{,}5 \cdot 10^{12}$ – $\approx 9{,}5 \cdot 10^{14}$	27 – 399	4.026.531.840 – 720.977.783.203.125
81–100	$\approx 2{,}5 \cdot 10^{15}$ – $\approx 9{,}9 \cdot 10^{17}$	44 – 2.550	773.967.052.800.000 – 879.461.151.930.399.473

• Test 1–20 có $n \le 10^6$ đúng như subtask 1; từ test 21 trở đi $n$ lên tới gần $10^{18}$.
• Đáp án có thể cách xa $n$: ví dụ test 100 có $n \approx 7{,}04 \cdot 10^{17}$ nhưng đáp án $\approx 6{,}12 \cdot 10^{17}$ – duyệt từng số từ $n$ đi xuống là vô vọng.
• $k$ lớn nhất là $2550 = 2 \cdot 3 \cdot 5^2 \cdot 17$: có nhiều cách tách thành $(t_1+1)(t_2+1)(t_3+1)$.

Subtask	Điều kiện	Các test	Cách ăn được
1 (20%)	$n \le 10^6$	1 – 20	Cách 1, 2
2 (30%)	$k \le 24$	21 – 50	Cách 2
3 (30%)	$k \le 400$	51 – 80	Cách 2
4 (20%)	không thêm	81 – 100	Cách 2

Ý tưởngĐoán bộ số mũ từ k, đoán bộ ba nguyên tố

Nếu $m = p_1^{t_1} p_2^{t_2} p_3^{t_3}$ thì mỗi ước của $m$ có dạng $p_1^{x} p_2^{y} p_3^{z}$ với $0 \le x \le t_1$, $0 \le y \le t_2$, $0 \le z \le t_3$, nên:

Công thức số ước

$$d(m) = (t_1 + 1)(t_2 + 1)(t_3 + 1) = k$$

Đặt $a = t_1 + 1$, $b = t_2 + 1$, $c = t_3 + 1$ (đều $\ge 2$): ta cần mọi cách viết $k = a \cdot b \cdot c$ có thứ tự (vì $p_1 < p_2 < p_3$ nên số mũ gán cho số nhỏ hay số lớn cho ra $m$ khác nhau). Với mỗi bộ $(a, b, c)$ và mỗi bộ ba nguyên tố liên tiếp $(p_i, p_{i+1}, p_{i+2})$:

Ứng viên

$$m = p_i^{\,a-1} \cdot p_{i+1}^{\,b-1} \cdot p_{i+2}^{\,c-1}$$

Khi $i$ tăng thì $m$ tăng, nên với mỗi $(a, b, c)$ ta duyệt $i = 0, 1, 2, \ldots$ tới khi $m > n$ thì dừng, ghi nhận $m$ lớn nhất. Vì $p_1 p_2 p_3 \le m \le 10^{18}$ nên $p_1 < 10^6$: chỉ cần sàng nguyên tố tới khoảng $10^6$.

Em nhập $n, k$ rồi bấm Tiếp để xem từng cách tách $k$ và bộ ba nguyên tố tốt nhất:

n = k =

Ví dụ nhanh:

Cách 1Duyệt m từ n giảm dần, phân tích từng số

Làm đúng theo đề: thử $m = n, n-1, \ldots$; với mỗi $m$ phân tích ra thừa số nguyên tố bằng cách thử chia tới $\sqrt{m}$, kiểm tra có đúng 3 thừa số, chúng liên tiếp (giữa hai thừa số kề nhau không có số nguyên tố nào) và số ước bằng $k$. Gặp $m$ đầu tiên thỏa là đáp án.

C++▶ Chạy tay từng dòng codeCách 1: thử m = n, n − 1, …; phân tích m bằng thử chia, kiểm tra 3 thừa số liên tiếp và số ước.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi lần phân tích tốn tới $\sqrt{m}$ phép chia. Với $n \le 10^6$ phần lớn test có đáp án gần $n$ nên chạy nhanh, nhưng vẫn có test đáp án nằm khá xa $n$ (phải phân tích hàng trăm nghìn số) nên bị quá thời gian.
• Khi $n$ cỡ $10^{12}$ trở lên, đáp án có thể cách $n$ hàng triệu, thậm chí hàng chục triệu tỉ đơn vị: không thể duyệt kịp.

Không gian$O(1)$

Thời gian$O\big((n - m) \sqrt{n}\big)$

Kết quả chạy thật: bản C++ đúng 18/100 test (Subtask 1: 18/20, Subtask 2: 0/30, Subtask 3: 0/30, Subtask 4: 0/20); bản Python đúng 17/100 (Subtask 1: 17/20, Subtask 2: 0/30, Subtask 3: 0/30, Subtask 4: 0/20).

Cách 2Duyệt cách tách k × bộ ba nguyên tố liên tiếp – Full điểm

Làm theo phần Ý tưởng: sàng nguyên tố tới $1{,}0001 \cdot 10^6$, duyệt mọi $(a, b, c)$ với $a \cdot b \cdot c = k$, rồi duyệt bộ ba $(p_i, p_{i+1}, p_{i+2})$ từ nhỏ đến lớn tới khi $m > n$. Lũy thừa và phép nhân phải chặn trên (không vượt $2 \cdot 10^{18}$) để không tràn long long.

C++▶ Chạy tay từng dòng codeCách 2 (minh hoạ với sàng nhỏ tới 100): duyệt k = a·b·c, với mỗi bộ (a, b, c) đi qua các bộ ba nguyên tố liên tiếp tới khi m > n.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Số bộ $(a, b, c)$ rất ít (với $k \le 2700$ chỉ vài trăm bộ), và vòng bộ ba dừng ngay khi $m > n$. Phần tốn thời gian nhất là sàng tới $10^6$.
• Hàm mul kiểm tra a > LIM / b trước khi nhân: nếu tràn thì trả về luôn LIM (lớn hơn mọi $n$), vòng lặp sẽ dừng đúng.
• Bản Python có số nguyên lớn nên tính thẳng pr[i] ** (a - 1) * ... không lo tràn.

Không gian$O(V)$, $V \approx 10^6$

Thời gian$O(V \log \log V + \text{số bộ } (a, b, c) \times \text{số bộ ba duyệt})$

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

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–20	Subtask 2 test 21–50	Subtask 3 test 51–80	Subtask 4 test 81–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	18/20	0/30	0/30	0/20	18/100	0,237s
Cách 1 – Python	17/20	0/30	0/30	0/20	17/100	0,505s
Cách 2 – C++	20/20	30/30	30/30	20/20	100/100	0,016s
Cách 2 – Python	20/20	30/30	30/30	20/20	100/100	0,175s

Ghi chú của mình: bài này là ví dụ đẹp cho kỹ thuật "đổi chiều duyệt": thay vì duyệt đáp án $m$ (tới $10^{18}$ giá trị), ta duyệt cấu trúc của đáp án – bộ số mũ (vài trăm cách) và bộ ba nguyên tố (dừng sớm khi vượt $n$). Công thức số ước $\prod (t_i + 1)$ là chìa khoá.

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 😇