Số đặc biệt (ver 2)

Nguồn: CLUE OJ – Map / Set Độ khó: Khá Số học Sàng nguyên tố

Đề bài

Sau khi tính toán cẩn thận, chia các đơn hàng một cách hợp lý, Thành đã mua được tất cả các món quà chỉ với số tiền là 117649 đồng. Mặc dù không liên quan đến việc mua bán này nhưng Thịnh nhận thấy rằng số 117649 rất đặc biệt, đó là nó không phải số nguyên tố nhưng lại có số các ước số dương là một số nguyên tố (số 117649 có đúng 7 ước dương), em gọi các số nguyên dương có tính chất như vậy là số "đặc biệt". Vốn rất yêu thích môn toán và những con số, Thịnh muốn đố các bạn giải bài toán như sau:

Yêu cầu: đếm số các số "đặc biệt" trong đoạn từ $L$ đến $R$.

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

Kết quả: đưa ra một số duy nhất là kết quả tìm được.

Ràng buộc:

• Có $\frac{1}{3}$ số test tương ứng với $\frac{1}{3}$ số điểm có $R \le 10^5$;
• Có $\frac{2}{3}$ số test còn lại tương ứng với $\frac{2}{3}$ số điểm không có ràng buộc gì thêm.

Ví dụ – input

2 5

Ví dụ – output

1

Lời mở đầu

Trong đoạn $[2, 5]$ chỉ có số 4 là "đặc biệt": 4 có 3 ước $\{1, 2, 4\}$, 3 là số nguyên tố, và 4 không phải số nguyên tố. Các số 2, 3, 5 có 2 ước (2 là số nguyên tố) nhưng bản thân chúng là số nguyên tố nên bị loại.

Bài này đẹp ở chỗ: cách "trâu" chỉ ăn được 1/3 số điểm, nhưng chỉ cần hai nhận xét toán học nhỏ là đi thẳng tới lời giải chạy trong tích tắc với $R = 10^{12}$. Mình sẽ đi từng bước một, mỗi bước là một cách giải chạy thật trên bộ test.

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ộ test100 test1/3Đếm ướcNhận xétp mũ chẵnCách 2Số chính phương100%Sàng + p^k

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

Bộ test có 100 test, mỗi test chỉ gồm 2 số $L, R$. Đề có 2 subtask: test 1–33 có $R \le 10^5$ (đúng 1/3 số test), test 34–100 có $R$ lớn dần tới $10^{12}$. Mình chia nhỏ subtask 2 theo độ lớn của $R$ để thấy rõ mỗi cách "gục" ở đâu (ô ghi số test bản C++ chạy đúng trong 1 giây, mình đo bằng thời gian CPU vì máy chấm thử đang chạy song song nhiều việc):

Test	R	Đáp án	Cách 1	Cách 2	Cách 3
1–33	$R ≤ 10^5$	0 – 79	33/33	33/33	33/33
34–50	$R < 10^6$	49 – 179	11/17	17/17	17/17
51–60	$R < 10^8$	182 – 1.233	0/10	10/10	10/10
61–70	$R < 10^{10}$	1.564 – 8.558	0/10	10/10	10/10
71–80	$R < 10^{11}$	8.966 – 25.893	0/10	10/10	10/10
81–90	$R < 10^{12}$	32.336 – 75.514	0/10	10/10	10/10
91–100	$R = 10^{12}$	78.705 – 78.711	0/10	10/10	10/10

• Hầu hết các test có $L$ rất nhỏ so với $R$ (đoạn gần như là $[1, R]$), càng về cuối thì $R - L$ càng lớn, tới gần $10^{12}$ – không thể duyệt từng số.
• 10 test cuối đều có $R = 10^{12}$, đáp án khoảng 78.700: gần như toàn bộ là các số $p^2$ với $p$ nguyên tố $\le 10^6$ (có 78.498 số nguyên tố như vậy).
• Có 4 test đáp án bằng 0 và 1 test $L = R$.

1/3Cách 1: đếm ước từng số

Làm đúng theo định nghĩa: duyệt mọi $x$ từ $L$ đến $R$, đếm số ước $d$ của $x$ (duyệt $i$ tới $\sqrt{x}$, mỗi ước $i$ đi kèm ước $x / i$), rồi kiểm tra $d$ có nguyên tố không. Điều kiện "$x$ không phải số nguyên tố" chính là $d \ne 2$, nên chỉ cần kiểm tra $d$ nguyên tố và $d \ne 2$.

C++▶ Chạy tay từng dòng codeCách 1: duyệt từng x, đếm ước trong O(√x) rồi kiểm tra số ước có nguyên tố không.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O((R - L + 1)\sqrt{R})$

Kết quả chạy thật: bản C++ đúng 44/100 test: toàn bộ 33 test subtask 1, cộng thêm 11 test đầu của subtask 2 (test 35, 36, 37, 38, 40, 41, 42, 43, 45, 48, 50) – các test này có $R < 10^6$ và đoạn $[L, R]$ dài không quá $5 \cdot 10^5$ nên vẫn kịp (chậm nhất 0.90 giây CPU). Từ test 51 ($R$ cỡ $10^7$ trở lên) thì chắc chắn quá thời gian. Bản Python chậm hơn nhiều, chỉ đúng 21/100 test – trượt cả vài test của subtask 1 có $R \approx 8 \cdot 10^4$–$10^5$. Vậy cách này chắc chắn được khoảng 1/3 số điểm.

Nhận xétSố đặc biệt trông như thế nào?

Trước khi tối ưu, hãy cho máy liệt kê thử các số đặc biệt nhỏ xem chúng có gì chung. Em nhập $L, R$ rồi bấm Tiếp để xem từng số được phân tích:

L = R =

Ví dụ nhanh:

Các số đặc biệt nhỏ là 4, 9, 16, 25, 49, 64, 81, 121, ... toàn là số chính phương, và hơn nữa đều là lũy thừa của đúng một số nguyên tố: $4 = 2^2$, $16 = 2^4$, $64 = 2^6$, $117649 = 7^6$. Không phải ngẫu nhiên đâu nhé:

Nhận xét 1 – số ước lẻ ⇔ số chính phương

Các ước của $x$ đi thành từng cặp $(i, x / i)$. Chỉ khi $x = s^2$ thì có cặp "trùng nhau" $(s, s)$ làm số ước bị lẻ. Số ước $d$ là số nguyên tố khác 2 thì phải là số lẻ ⇒ $x$ phải là số chính phương. Vậy chỉ cần xét $x = s^2$ với $\sqrt{L} \le s \le \sqrt{R} \le 10^6$.

Nhận xét 2 – công thức số ước

Nếu $x = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$ thì số ước là $d(x) = (e_1 + 1)(e_2 + 1) \cdots (e_m + 1)$. Một số nguyên tố không thể là tích của từ 2 thừa số lớn hơn 1, nên $x$ chỉ có đúng một thừa số nguyên tố: $x = p^k$ và $d(x) = k + 1$ phải là số nguyên tố lẻ, tức $k \in \{2, 4, 6, 10, 12, 16, \ldots\}$.

Sát nútCách 2: chỉ xét các số chính phương

Dùng nhận xét 1: thay vì duyệt $x$, ta duyệt $s$ từ $\lceil \sqrt{L} \rceil$ đến $\lfloor \sqrt{R} \rfloor$, phân tích $s$ ra thừa số nguyên tố $s = \prod p^{e}$ thì $s^2 = \prod p^{2e}$ nên $d(s^2) = \prod (2e + 1)$. Số lượng $s$ giảm từ $10^{12}$ xuống còn $10^6$.

C++▶ Chạy tay từng dòng codeCách 2: chỉ xét x = s², đếm ước của s² qua phân tích thừa số nguyên tố của s.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sqrtl trả về số thực nên có thể lệch 1 đơn vị với số rất lớn; hai vòng while ở dòng 28–29 chỉnh lại cho chắc chắn lo là số nhỏ nhất có lo*lo ≥ L và hi là số lớn nhất có hi*hi ≤ R.
2. Trong divOfSquare, sau vòng lặp nếu s > 1 thì phần còn lại là một số nguyên tố mũ 1, đóng góp thừa số $2 \cdot 1 + 1 = 3$.

Không gian$O(1)$

Thời gian$O(\sqrt{R} \cdot \sqrt[4]{R})$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất (trong các test đúng) 0.71 giây; nghĩa là trên máy của mình cách này vẫn qua hết, nhưng chỉ sát nút: các test $R \approx 10^{12}$ phải phân tích gần $10^6$ số $s$, mỗi số tốn tới $\sqrt{s} = 1000$ phép chia (với $s$ nguyên tố), tổng cỡ vài trăm triệu phép chia/lấy dư – máy chấm chậm hơn một chút là quá giờ. Bản Python đúng 72/100 test.

100%Cách 3: liệt kê thẳng các số p^k

Dùng nhận xét 2: số đặc biệt là $p^k$ với $p$ nguyên tố và $k + 1$ nguyên tố lẻ. Vì $p^k \le R \le 10^{12}$ và $k \ge 2$ nên $p \le 10^6$. Ta sàng Eratosthenes các số nguyên tố tới $10^6$, rồi với mỗi $p$ nhân dần $p^2, p^3, p^4, \ldots$ cho tới khi vượt $R$, đếm những lũy thừa thuộc $[L, R]$ có $k + 1$ nguyên tố.

Em nhập $L, R$ (tới 3000) rồi bấm Tiếp để xem lần lượt từng số nguyên tố $p$ "sinh" ra các số đặc biệt:

L = R =

Ví dụ nhanh:

C++▶ Chạy tay từng dòng codeCách 3: sàng nguyên tố rồi liệt kê các lũy thừa p^k ≤ R, đếm những số có k+1 nguyên tố.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần lưu các số đặc biệt rồi sắp xếp: mỗi số $p^k$ ứng với đúng một cặp $(p, k)$ (phân tích ra thừa số nguyên tố là duy nhất), nên đếm thẳng không sợ trùng.
2. Dòng if (x > R / p) break; kiểm tra "nhân thêm $p$ có vượt $R$ không" bằng phép chia, tránh trường hợp x * p tràn long long.
3. Số mũ $k$ lớn nhất chỉ khoảng 39 ($2^{39} \approx 5.5 \cdot 10^{11}$), nên gọi isPrime(k + 1) rất rẻ.
4. Bản Python mình tối ưu thêm: với $k = 2$ chỉ cần đếm số nguyên tố trong $[\lceil\sqrt{L}\rceil, \lfloor\sqrt{R}\rfloor]$ bằng bisect; các $k \ge 4$ chỉ xảy ra với $p \le 1000$.

Không gian$O(\sqrt{R})$

Thời gian$O(\sqrt{R} \log\log \sqrt{R})$

Kết quả chạy thật: đúng 100/100 test, thời gian CPU lớn nhất chỉ 0.01 giây (phần lớn là thời gian sàng $10^6$ số). Bản Python đúng 100/100 test, chậm nhất 0.11 giây.

Ghi chú của mình: đã chạy thật cả 3 cách trên bộ 100 test (đo thời gian CPU, giới hạn 1 giây). Cách 1 (đếm ước từng số): C++ 44/100, Python 21/100. Cách 2 (chỉ xét số chính phương): C++ 100/100, Python 72/100. Cách 3 (sàng + liệt kê $p^k$): C++ 100/100, Python 100/100. Bài nằm trong contest Map/Set nhưng lời giải đẹp nhất lại là số học thuần tuý – không cần map hay set nào cả 😄.

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 😇