Cặp tương đồng

Nguồn: CLUE OJ – Map/Set Độ khó: Trung bình Map Set Sàng nguyên tố

Đề bài

Hai số nguyên dương $A$ và $B$ được gọi là một cặp số tương đồng nếu như chúng có chung tập các ước nguyên tố. Ví dụ: $12$ và $18$ là cặp số tương đồng vì có chung tập ước nguyên tố là $\{2, 3\}$.

Cho trước hai số nguyên dương $L$ và $R$, hãy đếm số lượng cặp tương đồng $A$ và $B$ mà $L \le A < B \le R$.

Dữ liệu: gồm một dòng duy nhất chứa hai số nguyên dương $L$ và $R$ $(L < R \le 10^6)$.

Kết quả: in ra kết quả bài toán.

Chú ý:

60% số test có $R - L \le 1000$;
40% số test còn lại không giới hạn gì thêm.

Giới hạn: 5 giây, 256 MB.

Ví dụ – input

1 10

Ví dụ – output

Giải thích: có 4 cặp số tương đồng đó là: $\{2, 4\}, \{2, 8\}, \{3, 9\}, \{4, 8\}$.

Lời mở đầu

Thoạt nhìn bài này là bài số học, nhưng chìa khoá lại nằm ở chỗ gom nhóm: thay vì so sánh từng cặp, ta tìm cho mỗi số một "chữ ký" sao cho hai số tương đồng khi và chỉ khi có cùng chữ ký, rồi dùng map đếm. Mình sẽ đi từ cách so từng cặp (subtask 1) tới cách gom nhóm (full), và cuối cùng tăng tốc bằng sàng. Tất cả đều chạy thật trên 100 test của CLUE OJ.

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

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

Bộ test100 test, 2 subtask Ý tưởngrad(x) + map Cách 1So từng cặp Cách 2Gom nhóm, thử chia Cách 3Sàng + map

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

Nhóm test	Số test	L	R	R − L	Đáp án	Số test đáp án = 0
1–60	60	10.338 – 483.579	11.148 – 484.386	702 – 898	0 – 4	53
61–100	40	32 – 488	700.428 – 896.007	700.065 – 895.774	1.332.881 – 1.720.544	0

Subtask	Điều kiện (theo đề)	Test	Thực tế trong bộ test
1 (60%)	$R - L \le 1000$	1 – 60	$R - L$ từ 702 đến 898, $R < 5 \cdot 10^5$
2 (40%)	không giới hạn thêm	61 – 100	$L < 500$, $R$ từ 700.428 đến 896.007 → gần như cả đoạn $[1, 10^6]$

Một điều thú vị: ở subtask 1 có tới 53/60 test đáp án bằng 0. Lý do là trong một đoạn ngắn khoảng 1000 số lớn cỡ $10^5$, hiếm khi có hai số có cùng tập ước nguyên tố (muốn vậy thì phần "lặp lại" của chúng phải khác nhau mà chênh lệch nhỏ hơn 1000). Còn subtask 2 thì đoạn gần như là cả $[1, 10^6]$, đáp án cỡ $1{,}7 \cdot 10^6$ cặp.

Ý tưởngChữ ký của một số: tích các ước nguyên tố khác nhau

Gọi $\text{rad}(x)$ là tích các ước nguyên tố khác nhau của $x$ (chỉ nhân mỗi số nguyên tố một lần). Ví dụ:

$12 = 2^2 \cdot 3$ → $\text{rad}(12) = 2 \cdot 3 = 6$;
$18 = 2 \cdot 3^2$ → $\text{rad}(18) = 6$;
$8 = 2^3$ → $\text{rad}(8) = 2$; $\text{rad}(7) = 7$; $\text{rad}(1) = 1$.

Mấu chốt

Theo định lý cơ bản của số học (mỗi số phân tích được thành tích các thừa số nguyên tố theo một cách duy nhất), hai tập ước nguyên tố bằng nhau $\iff$ $\text{rad}$ bằng nhau. Vậy ta chia các số trong $[L, R]$ thành các nhóm có cùng $\text{rad}$. Nhóm nào có $c$ số thì đóng góp $\frac{c(c-1)}{2}$ cặp.

Để đếm số lượng mỗi nhóm ta dùng map<int, int> cnt với cnt[r] = số số có $\text{rad} = r$. Em nhập $L$, $R$ rồi bấm Tiếp để xem từng số được tính chữ ký và bỏ vào nhóm:

L R

Ví dụ nhanh:

Cách 1So sánh từng cặp – Subtask 1

Làm đúng theo định nghĩa: phân tích từng số ra tập ước nguyên tố (thử chia $i$ từ 2 tới $\sqrt{x}$), lưu thành vector tăng dần, rồi so sánh từng cặp. Hai vector so sánh bằng == được luôn (cùng độ dài, cùng từng phần tử).

C++▶ Chạy tay từng dòng codeCách 1: phân tích từng số ra tập ước nguyên tố rồi so sánh từng cặp.

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

Dữ liệu mẫu:

Trong primeSet, gặp ước i thì chia hết i ra khỏi x (vòng while), nhờ vậy về sau chỉ có số nguyên tố mới chia hết x, và mỗi số nguyên tố chỉ được thêm một lần.
Sau vòng for nếu x > 1 thì phần còn lại là một số nguyên tố lớn hơn $\sqrt{x}$ ban đầu.
Số cặp là $\frac{m(m-1)}{2}$ với $m = R - L + 1$: subtask 1 chỉ khoảng $4 \cdot 10^5$ cặp, nhưng subtask 2 lên tới $4 \cdot 10^{11}$ cặp.

Không gian$O(m \log R)$

Thời gian$O(m\sqrt{R} + m^2 \log R)$

Kết quả chạy thật: bản C++ đúng 60/100 test – ăn trọn Subtask 1; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy dưới 0,01s. Bản Python đúng 60/100 test – ăn trọn Subtask 1; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy 0,09s.

Cách 2Gom nhóm theo rad bằng map – Full điểm

Thay vì so từng cặp, mỗi số chỉ cần tính $\text{rad}$ một lần rồi cnt[rad(x)]++. Cuối cùng duyệt map cộng $\frac{c(c-1)}{2}$.

C++▶ Chạy tay từng dòng codeCách 2: tính rad(x) bằng thử chia, gom nhóm bằng map, cộng c(c−1)/2.

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

Dữ liệu mẫu:

Hàm rad giống hệt primeSet, chỉ thay việc push_back bằng phép nhân r *= i. Vì $x \le 10^6$ nên $\text{rad}(x) \le x$ vẫn vừa int.
c * (c - 1) / 2 tính bằng long long cho an toàn (nhóm $\text{rad} = 2$ – các luỹ thừa của 2 – chỉ có 20 số, nhưng nhóm lớn nhất có thể lớn hơn nhiều).
Thử chia tới $\sqrt{x} \le 1000$ cho mỗi số, cả đoạn $10^6$ số tốn khoảng vài trăm triệu phép chia – vẫn kịp trong 5 giây.

Không gian$O(m)$

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

Kết quả chạy thật: bản C++ đúng 100/100 test – ăn trọn Subtask 1, Subtask 2; test đúng chậm nhất chạy 0,67s. Bản Python đúng 60/100 test – ăn trọn Subtask 1; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy 0,04s – vòng thử chia viết bằng Python quá chậm cho $10^6$ số.

Cách 3Sàng ước nguyên tố nhỏ nhất – nhanh hơn nhiều

Thử chia cho từng số vẫn lãng phí. Ta dùng sàng để tính trước spf[x] = ước nguyên tố nhỏ nhất của $x$ với mọi $x \le R$. Khi đó phân tích $x$ chỉ mất $O(\log x)$ bước: lấy p = spf[y], nhân vào $\text{rad}$, chia hết $p$ ra khỏi $y$, lặp lại.

C++▶ Chạy tay từng dòng codeCách 3: sàng spf, phân tích nhanh từng số, gom nhóm bằng map.

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

Dữ liệu mẫu:

Vòng sàng: với mỗi $i$ chưa có spf (tức $i$ nguyên tố), gán spf[j] = i cho các bội $j$ của $i$ chưa được gán. Tổng chi phí $O(R \log \log R)$.
Bản Python mình làm hơi khác: sàng thẳng ra mảng rad bằng cách nhân mỗi số nguyên tố $p$ vào mọi bội của nó – vòng range(p, R + 1, p) chạy nhanh hơn việc phân tích từng số.

Không gian$O(R)$

Thời gian$O(R \log\log R + m \log m)$

Kết quả chạy thật: bản C++ đúng 100/100 test – ăn trọn Subtask 1, Subtask 2; test đúng chậm nhất chạy 0,35s. Bản Python đúng 100/100 test – ăn trọn Subtask 1, Subtask 2; test đúng chậm nhất chạy 0,82s.

Tổng kếtKết quả chạy thật của các cách

Cách	Subtask 1 test 1–60	Subtask 2 test 61–100	Tổng	Chậm nhất (test đúng)
Cách 1 – C++	60/60	0/40 quá thời gian	60/100	0,01s
Cách 1 – Python	60/60	0/40 quá thời gian	60/100	0,09s
Cách 2 – C++	60/60	40/40	100/100	0,67s
Cách 2 – Python	60/60	0/40 quá thời gian	60/100	0,04s
Cách 3 – C++	60/60	40/40	100/100	0,35s
Cách 3 – Python	60/60	40/40	100/100	0,82s

Ghi chú của mình: số liệu trên là chạy thật trên 100 test của CLUE OJ với giới hạn 5 giây, thời gian là thời gian CPU đo trên máy của mình (biên dịch g++ -O2). Cách 2 và cách 3 bản C++ đều đạt 100/100 test; cách 3 nhanh hơn rõ rệt nhờ sàng.

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 😇

Lập Trình Thuật Toán