Đếm cặp thỏa mãn

Nguồn: CLUE OJ – Chương 47: Các bài tập về số nguyên tố Độ khó: Trung bình Chữ số tận cùng Đếm theo nhóm

Đề bài

Hãy đếm số lượng các cặp vị trí $(i, j)$ với $i < j$ sao cho $a[i] \cdot a[j]$ có tồn tại số $0$ ở tận cùng bên phải.

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương $N \le 10^6$ là số lượng phần tử trong mảng.
• Dòng tiếp theo chứa $N$ số nguyên dương $a[i]$ $(a[i] \le 10^{18})$ là danh sách các phần tử trong mảng, mỗi số cách nhau bởi 1 khoảng trắng.

Đầu ra: in ra 1 số nguyên duy nhất là số lượng các cặp thỏa mãn.

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

Subtask:

• $30\%$ đầu tiên có $N \le 10^4$ và $a[i] \le 10^9$.
• $20\%$ tiếp theo có $N \le 10^4$ và $a[i] \le 10^{18}$.
• $40\%$ tiếp theo có $N \le 10^5$ và $a[i] \le 10^{18}$.
• $10\%$ cuối cùng không có ràng buộc gì thêm.

Ví dụ – input

4
19 16 5 10

Ví dụ – output

4

Giải thích ví dụ: có 4 cặp vị trí thỏa mãn: $(1, 4)$: $19 \cdot 10 = 190$; $(2, 3)$: $16 \cdot 5 = 80$; $(2, 4)$: $16 \cdot 10 = 160$; $(3, 4)$: $5 \cdot 10 = 50$. Các cặp còn lại $19 \cdot 16 = 304$, $19 \cdot 5 = 95$ không tận cùng bằng $0$.

Lời mở đầu

"Có số $0$ ở tận cùng bên phải" nghĩa là chữ số hàng đơn vị của tích bằng $0$, tức tích chia hết cho $10$. Cái bẫy của bài: $a[i]$ tới $10^{18}$ nên tích tới $10^{36}$, tràn mọi kiểu số nguyên của C++. Và $N$ tới $10^6$ thì không thể xét đủ $\approx 5 \cdot 10^{11}$ cặp. Mình sẽ đi từ cách nhân thẳng (ăn subtask 1), sang cách chỉ giữ chữ số tận cùng, rồi tới cách đếm theo 10 nhóm chạy $O(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, 4 subtaskÝ tưởngchỉ cần chữ số cuốiCách 1nhân thẳngCách 2chữ số cuối, O(N²)Cách 3đếm 10 nhómTổ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 4 nhóm như subtask:

Test	N	Giá trị $a[i]$	Đáp án
1–30	5 – 10.000	1 … $\approx 10^9$	0 – 12.830.458
31–50	10.000	$\approx 10^8$ … $\approx 10^{18}$	13.161.329 – 14.015.448
51–90	100.000	$\approx 10^8$ … $\approx 10^{18}$	1.330.913.761 – 1.369.104.459
91–100	1.000.000	$\approx 10^8$ … $\approx 10^{18}$	134.417.099.477 – 135.392.308.943

• Đáp án lớn nhất cỡ $1{,}35 \cdot 10^{11}$, vượt int nên biến đếm phải là long long.
• Test 31–100 có $a[i]$ tới gần $10^{18}$: tích hai số tới $10^{36}$, không kiểu số nguyên nào của C++ chứa nổi.
• Test 91–100 có $N = 10^6$, tức gần $5 \cdot 10^{11}$ cặp – bắt buộc phải đếm mà không duyệt từng cặp.

Subtask	Điều kiện	Các test	Cách ăn được
1 (30%)	$N \le 10^4$, $a[i] \le 10^9$	1 – 30	Cách 1, 2, 3
2 (20%)	$N \le 10^4$, $a[i] \le 10^{18}$	31 – 50	Cách 2, 3
3 (40%)	$N \le 10^5$	51 – 90	Cách 3
4 (10%)	$N \le 10^6$	91 – 100	Cách 3

Ý tưởngTích tận cùng bằng 0 chỉ phụ thuộc chữ số cuối

Chữ số hàng đơn vị của tích $x \cdot y$ chính là $(x \bmod 10) \cdot (y \bmod 10) \bmod 10$ – vì phép nhân "giữ nguyên" khi lấy dư:

Tính chất

$$(x \cdot y) \bmod 10 = \big((x \bmod 10) \cdot (y \bmod 10)\big) \bmod 10$$

Ví dụ $19 \cdot 16 = 304$: chữ số cuối là $4 = 9 \cdot 6 \bmod 10$. Vậy ta không cần biết cả số, chỉ cần chữ số tận cùng $c = a[i] \bmod 10 \in \{0, 1, \ldots, 9\}$. Các cặp chữ số $(c_1, c_2)$ cho tích tận cùng $0$ là:

• có một chữ số bằng $0$: $(0, \text{bất kỳ})$;
• một số bằng $5$, số kia chẵn: $(5, 2), (5, 4), (5, 6), (5, 8)$.

Gọi $cnt[c]$ là số phần tử có chữ số cuối là $c$. Mỗi cặp nhóm $(c_1, c_2)$ hợp lệ góp $cnt[c_1] \cdot cnt[c_2]$ cặp nếu $c_1 \ne c_2$, hoặc $\binom{cnt[c]}{2} = \frac{cnt[c](cnt[c]-1)}{2}$ cặp nếu cùng nhóm ($c_1 = c_2 = 0$). Em nhập mảng rồi bấm Tiếp để xem cách đếm:

Mảng a:

Ví dụ nhanh:

Cách 1Nhân thẳng từng cặp – chỉ đúng khi a[i] ≤ 10⁹

Cách "nghe sao làm vậy": duyệt mọi cặp $i < j$, tính tích rồi xem tich % 10 == 0. Với $a[i] \le 10^9$ thì tích $\le 10^{18}$ vẫn vừa unsigned long long (tối đa $\approx 1{,}8 \cdot 10^{19}$).

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi cặp i < j, nhân thẳng rồi xét chữ số cuối của tích.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Có $\frac{N(N-1)}{2}$ cặp: với $N = 10^4$ là khoảng $5 \cdot 10^7$ phép nhân – vẫn chạy kịp.
• Khi $a[i]$ lên tới $10^{18}$, tích vượt $2^{64}$ và bị tràn số: máy chỉ giữ phần dư của tích khi chia cho $2^{64}$, chữ số cuối của phần dư này không còn là chữ số cuối của tích thật. Em thử nhập vào khung chạy tay hai số lớn như 2\n1000000000000000001 999999999999999999 để thấy.
• Bản Python có số nguyên lớn nên không tràn, nhưng duyệt $O(N^2)$ bằng Python rất chậm.

Không gian$O(N)$

Thời gian$O(N^2)$

Kết quả chạy thật: bản C++ đúng 30/100 test (Subtask 1: 30/30, Subtask 2: 0/20, Subtask 3: 0/40, Subtask 4: 0/10); bản Python đúng 10/100 (Subtask 1: 10/30, Subtask 2: 0/20, Subtask 3: 0/40, Subtask 4: 0/10). Bản C++ sai cả 20 test của subtask 2 vì tràn số, còn subtask 3, 4 thì quá thời gian. Bản Python không bị tràn số nhưng vòng đôi $O(N^2)$ quá chậm, chỉ kịp các test có $N$ nhỏ.

Cách 2Chỉ giữ chữ số tận cùng – hết tràn số, vẫn O(N²)

Áp dụng tính chất ở phần Ý tưởng: lúc đọc ta lưu luôn $d[i] = a[i] \bmod 10$, rồi xét cặp bằng d[i] * d[j] % 10 == 0. Tích hai chữ số tối đa $81$ nên không bao giờ tràn.

C++▶ Chạy tay từng dòng codeCách 2: lưu chữ số tận cùng d[i] = a[i] % 10, rồi duyệt mọi cặp i < j.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Đọc $a[i]$ vào long long (tối đa $\approx 9{,}2 \cdot 10^{18}$, đủ cho $10^{18}$) rồi lấy dư ngay.
• Đã hết lỗi tràn số nên ăn trọn subtask 2. Nhưng vẫn là $O(N^2)$: $N = 10^5$ đã là $5 \cdot 10^9$ cặp – quá thời gian.

Không gian$O(N)$

Thời gian$O(N^2)$

Kết quả chạy thật: bản C++ đúng 50/100 test (Subtask 1: 30/30, Subtask 2: 20/20, Subtask 3: 0/40, Subtask 4: 0/10); bản Python đúng 10/100 (Subtask 1: 10/30, Subtask 2: 0/20, Subtask 3: 0/40, Subtask 4: 0/10) – vòng đôi của Python chậm hơn C++ hàng chục lần.

Cách 3Đếm theo 10 nhóm chữ số tận cùng – O(N)

Các số cùng chữ số tận cùng "cư xử" giống hệt nhau, nên thay vì xét từng cặp số ta xét từng cặp nhóm: chỉ có $10$ nhóm, tức tối đa $55$ cặp nhóm $(c_1 \le c_2)$. Đếm $cnt[c]$ trong lúc đọc, rồi cộng $cnt[c_1] \cdot cnt[c_2]$ (hoặc $\binom{cnt[c]}{2}$ khi $c_1 = c_2$) cho các cặp nhóm hợp lệ.

C++▶ Chạy tay từng dòng codeCách 3: đếm cnt[0..9] theo chữ số tận cùng, rồi cộng số cặp của từng cặp nhóm (c1, c2) có c1·c2 tận cùng 0.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng đôi c1, c2 chỉ chạy $55$ lần, không phụ thuộc $N$. Toàn bộ thời gian là đọc dữ liệu $O(N)$ – vì vậy nhớ có ios::sync_with_stdio(0); cin.tie(0); khi đọc $10^6$ số.
• cnt khai báo long long để phép nhân cnt[c1] * cnt[c2] (tới $\approx 2{,}5 \cdot 10^{11}$) không tràn int.
• Bản Python không cần đổi cả chuỗi sang số: x[-1] - 48 lấy thẳng mã ASCII của chữ số cuối, nhanh hơn int(x) % 10 nhiều.

Không gian$O(N)$ (đọc dữ liệu), $O(1)$ cho phần đếm

Thời gian$O(N + 10^2)$

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

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

Lời giải	Subtask 1 test 1–30	Subtask 2 test 31–50	Subtask 3 test 51–90	Subtask 4 test 91–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	30/30	0/20	0/40	0/10	30/100	0,075s
Cách 1 – Python	10/30	0/20	0/40	0/10	10/100	0,032s
Cách 2 – C++	30/30	20/20	0/40	0/10	50/100	0,090s
Cách 2 – Python	10/30	0/20	0/40	0/10	10/100	0,035s
Cách 3 – C++	30/30	20/20	40/40	10/10	100/100	0,183s
Cách 3 – Python	30/30	20/20	40/40	10/10	100/100	0,444s

Ghi chú của mình: bài này "đội lốt" số lớn nhưng thực chất chỉ cần chữ số tận cùng. Cách 1 vừa tràn số vừa chậm; cách 2 sửa được tràn số; cách 3 gom các số cùng chữ số cuối thành nhóm nên chỉ còn $O(N)$. Kỹ thuật "đếm theo nhóm số dư rồi ghép cặp nhóm" gặp rất nhiều trong các bài đếm cặp có tổng/tích chia hết cho $k$.

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 😇