Mã khóa

Nguồn: Đề tuyển sinh lớp 10 Trường Phổ thông Năng khiếu 2012 – 2013 (Bài 4) Độ khó: Trung bình Sàng nguyên tố Ước nguyên tố

Đề bài

Để mở cửa kho báu, bạn cần tìm được chìa khóa bí mật. Quy tắc để xác định chìa khóa bí mật như sau: cho trước số nguyên dương $N$, chìa khóa bí mật $K$ là số nguyên dương lớn nhất không vượt quá $N$ và có số lượng ước số nguyên tố khác nhau nhiều nhất.

Yêu cầu: tìm chìa khóa bí mật $K$ tương ứng với số nguyên dương $N$ cho trước.

Dữ liệu vào: từ tệp văn bản KEY.INP gồm một dòng duy nhất chứa số nguyên dương $N$ $(2 \le N \le 10^6)$.

Kết quả: ghi ra tệp văn bản KEY.OUT số nguyên dương $K$.

Giới hạn: thời gian 0,3 giây (thầy đặt chặt hơn đề gốc 1 giây vì máy chấm CLUE rất mạnh), bộ nhớ 256 MB.

Ví dụ – KEY.INP

29

Ví dụ – KEY.OUT

28

Giải thích ví dụ: trong các số từ $2$ tới $29$, số có nhiều ước nguyên tố khác nhau nhất có $2$ ước (ví dụ $6, 10, 12, \ldots, 28$). Số lớn nhất trong đó là $K = 28 = 2^2 \cdot 7$.

Lưu ý nộp bài: bài đọc/ghi tệp KEY.INP / KEY.OUT. Code C++ dùng if (fopen("KEY.INP", "r")) { freopen(...); freopen(...); }, bản Python dùng os.path.exists("KEY.INP"): có tệp thì đọc tệp, không có thì đọc bàn phím.

Lời mở đầu

Bài này đếm "số ước nguyên tố khác nhau" (ký hiệu $\omega(x)$) cho mọi số từ $2$ tới $N$ rồi lấy số lớn nhất có $\omega$ lớn nhất. Cái khó nằm ở giới hạn 0,3 giây: phân tích từng số bằng thử chia sẽ không kịp. Mình đi từ cách thử chia từng số, tới sàng đếm ước nguyên tố, và cuối cùng là một mẹo toán học rất gọn: tích các số nguyên tố đầu tiên.

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Ý tưởngđếm ω(x)Cách 1thử chia từng sốCách 2sàng đếm ướcCách 3tích nguyên tố đầuTổng kếtkết quả chạy thật

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

Đề không chia subtask, mình chia 100 test thành 4 nhóm theo $N$:

Nhóm	Test	N	Đáp án K	N − K
1	1 – 20	3 … 929	3 … 924	0 … 117
2	21 – 50	231 … 9.577	210 … 9.570	7 … 735
3	51 – 80	12.023 … 130.074	12.012 … 129.030	11 … 8.517
4	81 – 100	101.073 … 532.420	101.010 … 510.510	45 … 21.910

• $N$ lớn nhất trong bộ test là $532\,420$ (đề cho tới $10^6$). Nhiều đáp án rơi đúng vào các số đẹp như $30\,030 = 2\cdot3\cdot5\cdot7\cdot11\cdot13$ hay $510\,510 = 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17$ – đó là gợi ý cho cách 3.
• Khoảng cách $N - K$ có thể lên tới hơn hai mươi nghìn, nên "đi lùi vài bước" không phải lúc nào cũng ngắn.

Ý tưởngω(x) lớn nhất đạt được là bao nhiêu?

Gọi $\omega(x)$ là số ước nguyên tố khác nhau của $x$. Nếu $\omega(x) = m$ thì $x$ chia hết cho $m$ số nguyên tố khác nhau, nên $x \ge$ tích của $m$ số nguyên tố nhỏ nhất:

Tích các số nguyên tố đầu tiên (primorial)

$$P_m = 2 \cdot 3 \cdot 5 \cdots p_m: \quad 2,\ 6,\ 30,\ 210,\ 2310,\ 30\,030,\ 510\,510,\ 9\,699\,690, \ldots$$

Vậy $\omega$ lớn nhất trong đoạn $[2, N]$ đúng bằng $m$ lớn nhất với $P_m \le N$ (và $P_m$ là một số đạt được). Với $N \le 10^6$ thì $m \le 7$.

Như ví dụ $N = 29$: $P_2 = 6 \le 29 < P_3 = 30$ nên $\omega$ lớn nhất là $2$, và $K$ là số lớn nhất $\le 29$ có đúng $2$ ước nguyên tố: $29$ (nguyên tố, $\omega = 1$) → $28 = 2^2 \cdot 7$ ($\omega = 2$). Em nhập $N$ rồi bấm Tiếp để xem:

N =

Ví dụ nhanh:

Cách 1Đếm ω(x) cho từng x bằng thử chia

Với mỗi $x$ từ $2$ tới $N$, phân tích $x$ bằng thử chia $p$ khi $p^2 \le x$, đếm số $p$ chia hết (mỗi $p$ chia hết thì chia hết luôn để $x$ không còn thừa số $p$). Giữ số $x$ có $\omega$ lớn nhất; dùng dấu >= để khi bằng nhau thì lấy số lớn hơn.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi x từ 2 tới N đếm số ước nguyên tố khác nhau bằng thử chia, giữ x lớn nhất có ω lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Phân tích mỗi $x$ tốn tới $\sqrt x$ bước khi $x$ nguyên tố hoặc có ước lớn, nhưng phần lớn các số có ước nhỏ nên vòng thử thu nhỏ rất nhanh. Tổng cộng vẫn là $O(N\sqrt N)$ trong trường hợp xấu.
• Thực tế với $N \approx 5 \cdot 10^5$ (lớn nhất trong bộ test) bản C++ chạy khoảng 0,27 giây – sát nút giới hạn 0,3 giây; mình thử thêm $N = 10^6$ thì mất 0,53 giây, quá giới hạn. Bản Python không kịp ngay từ $N$ cỡ $10^5$.

Không gian$O(1)$

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

Kết quả chạy thật: bản C++ đúng 100/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 20/20), test đúng chạy lâu nhất 0,268 giây; bản Python đúng 70/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 20/30, Nhóm 4: 0/20), test đúng chạy lâu nhất 0,242 giây; 30 test quá thời gian.

Cách 2Sàng đếm số ước nguyên tố cho mọi x ≤ N

Biến thể của sàng Eratosthenes: mảng cnt[x] ban đầu bằng $0$. Duyệt $p = 2, 3, \ldots, N$; nếu cnt[p] == 0 thì chưa có số nguyên tố nhỏ hơn nào chia hết $p$, tức $p$ nguyên tố – ta cộng $1$ vào cnt của mọi bội của $p$. Cuối cùng cnt[x] $= \omega(x)$.

C++▶ Chạy tay từng dòng codeCách 2: sàng – mỗi số nguyên tố p cộng 1 vào cnt của mọi bội của p; rồi tìm x lớn nhất có cnt lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi số nguyên tố $p$ duyệt $N/p$ bội; tổng $\sum_{p \le N} N/p \approx N \ln\ln N$ – chỉ vài triệu phép cộng.
• Mảng cnt $10^6$ phần tử khai báo toàn cục.
• Bản Python của cách này phải chạy vòng lặp hàng triệu bước bằng Python thuần, khó lọt 0,3 giây.

Không gian$O(N)$

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

Kết quả chạy thật: bản C++ đúng 100/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 20/20), test đúng chạy lâu nhất 0,013 giây; bản Python đúng 90/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 10/20), test đúng chạy lâu nhất 0,132 giây; 10 test quá thời gian.

Cách 3Tính m từ tích các số nguyên tố đầu, rồi đi lùi từ N

Dùng nhận xét ở phần Ý tưởng: nhân dần $2 \cdot 3 \cdot 5 \cdots$ khi tích còn $\le N$ để có $m$ – số ước nguyên tố nhiều nhất có thể. Sau đó đi lùi $K = N, N - 1, \ldots$ và dừng ở số đầu tiên có $\omega(K) = m$ (phân tích bằng thử chia). Không cần mảng, và thường chỉ phải kiểm tra vài trăm tới vài chục nghìn số.

C++▶ Chạy tay từng dòng codeCách 3: nhân 2·3·5·… để biết ω lớn nhất m, rồi đi lùi từ N tới số đầu tiên có ω = m.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng nhân chỉ chạy tối đa 7 lần với $N \le 10^6$; mảng 10 số nguyên tố đầu là đủ dùng.
• Số bước lùi phụ thuộc $N$: trong bộ test nhiều nhất là $21\,910$ bước, mỗi bước phân tích tốn tối đa $\sqrt{N} \approx 1000$ phép chia, nhưng đa số dừng sớm.
• Cách này không cần mảng nên bản Python cũng nhẹ hơn hẳn cách 2.

Không gian$O(1)$

Thời gian$O(\text{số bước lùi} \cdot \sqrt N)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 20/20), test đúng chạy lâu nhất 0,021 giây; bản Python đúng 97/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 17/20), test đúng chạy lâu nhất 0,188 giây; 3 test quá thời gian.

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 0,3 giây, đo thời gian CPU:

Lời giải	Nhóm 1 test 1–20	Nhóm 2 test 21–50	Nhóm 3 test 51–80	Nhóm 4 test 81–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	20/20	30/30	30/30	20/20	100/100	0,268s
Cách 1 – Python	20/20	30/30	20/30	0/20	70/100	0,242s
Cách 2 – C++	20/20	30/30	30/30	20/20	100/100	0,013s
Cách 2 – Python	20/20	30/30	30/30	10/20	90/100	0,132s
Cách 3 – C++	20/20	30/30	30/30	20/20	100/100	0,021s
Cách 3 – Python	20/20	30/30	30/30	17/20	97/100	0,188s

Ghi chú của mình: cả 3 cách đều cho đáp án đúng ở mọi test chạy kịp. Bản C++ của cách 1 qua hết bộ test nhưng chỉ cách giới hạn 0,03 giây (với $N = 10^6$ sẽ quá thời gian). Cách 2 (sàng đếm ước) và cách 3 (tích các số nguyên tố đầu + đi lùi) mới là lời giải an toàn, chỉ vài phần trăm giây. Với Python, cách 3 tốt nhất (97/100) vì không phải chạy vòng lặp sàng hàng triệu bước; 3 test còn lại có $N$ ngay trên $510\,510$ nên phải lùi từ khoảng 18 tới 22 nghìn số. Bài học: số có nhiều ước nguyên tố nhất ≤ N gắn với tích các số nguyên tố đầu tiên 2·3·5·7·…

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 😇