Dãy tương đương

Nguồn: Tuyển sinh lớp 10 PTNK 2016–2017 Độ khó: Trung bình Map / Set Phân tích thừa số nguyên tố

Đề bài

Bài 3. SEQUENCE – Dãy tương đương

Nam định nghĩa dãy $a$ gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ tương đương với dãy $b$ gồm $m$ số nguyên dương $b_1, b_2, \ldots, b_m$ nếu tích các phần tử của dãy $a$ bằng tích các phần tử của dãy $b$.

Yêu cầu: Giúp Nam kiểm tra hai dãy cho trước có tương đương hay không?

Input: dòng đầu chứa số nguyên $t$ là số bộ test cần kiểm tra $(1 \le t \le 3)$. Tiếp theo là $t$ nhóm dòng, mỗi nhóm dòng mô tả một bộ test gồm:

• Dòng đầu là hai số nguyên $n$ và $m$ $(1 \le n, m \le 100)$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$.
• Dòng thứ ba chứa $m$ số nguyên dương $b_1, b_2, \ldots, b_m$ $(1 \le b_j \le 10^9)$.

Output: gồm $t$ dòng, dòng thứ $i$ ghi từ YES hoặc NO tương ứng với bộ test thứ $i$ là tương đương hay không tương đương.

Lưu ý trên CLUE OJ: dữ liệu nhập xuất chuẩn từ bàn phím và in ra màn hình (đề gốc có kêu đọc từ file thì các bạn cứ kệ nó nhé).

Ví dụ – input

2
2 3
10 3
2 3 5
3 3
2 4 7
8 1 5

Ví dụ – output

YES
NO

Lời mở đầu

Đọc đề thấy dễ ợt: nhân hết dãy $a$, nhân hết dãy $b$, so sánh là xong! Nhưng khoan – mỗi số tới $10^9$, nhân 100 số thì tích có thể dài tới 900 chữ số, không kiểu số nguyên nào của C++ chứa nổi. Bài này là ví dụ rất hay để thấy tràn số nguy hiểm thế nào (code sai mà vẫn được tới 88 điểm!), và cách dùng map để lưu số mũ các thừa số nguyên tố thay cho cả con số khổng lồ.

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, không subtaskÝ tưởngso số mũCách 1nhân thẳng – saiCách 2map số mũCách 3giản ước UCLN

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

Số test	Số bộ (t)	Tổng số bộ	YES / NO	n. m	Giá trị lớn nhất	Tích dài nhất
100	t = 3 ở mọi test	300	221 / 79	1 … 100	813.966.205	411 chữ số

• Đề không chia subtask: test nào cũng có $t = 3$ bộ, $n, m$ tới 100 (có 227 bộ có $n$ hoặc $m$ đúng bằng 100). Vì thế không có "điểm an ủi" cho cách làm chậm – nhưng bù lại chỉ cần đúng là được, vì $n, m$ nhỏ.
• Phần lớn các số chỉ cỡ vài chục nghìn, nhưng có 99 bộ chứa số lớn (tới gần $9 \cdot 10^8$), có cả những số nguyên tố lớn – cách phân tích thừa số phải xử lý được "phần dư cuối cùng là một số nguyên tố lớn".
• Các tích dài tới 411 chữ số. Có những bộ hai tích dài bằng đúng nhau (cùng số chữ số) mà vẫn khác nhau, nên đoán theo độ dài là không được.
• Bẫy tràn số: ở các test 31, 34, 39, 47, 50, 52, 53, 63, 70, 87, 91, 100, có bộ mà hai tích khác nhau nhưng đều chia hết cho $2^{64}$. Khi nhân bằng long long, kết quả bị "quay vòng" theo $2^{64}$ nên cả hai đều thành 0 → code in nhầm YES.

Ý tưởngSo sánh "bộ gen" nguyên tố thay vì so sánh con số

Theo định lý cơ bản của số học, mỗi số nguyên dương phân tích ra thừa số nguyên tố theo đúng một cách. Tích của cả dãy cũng vậy: số mũ của nguyên tố $p$ trong tích = tổng số mũ của $p$ trong từng số. Do đó:

Thuật toán

Dùng map<int, int> mu. Phân tích từng $a_i$: mỗi thừa số $p$ thì mu[p] += 1. Phân tích từng $b_j$: mỗi thừa số $p$ thì mu[p] -= 1. Hai tích bằng nhau ⇔ cuối cùng mọi mu[p] đều bằng 0.

Vì sao dùng map? Các thừa số nguyên tố có thể lớn tới $10^9$ (ví dụ chính $a_i$ là số nguyên tố) nên không dùng mảng đếm được; còn số thừa số khác nhau thì rất ít (mỗi số $\le 10^9$ có không quá 9 thừa số nguyên tố khác nhau).

Em nhập 2 dãy rồi bấm Tiếp để xem từng số được "tách" ra và cộng/trừ vào map:

Dãy a: Dãy b:

Ví dụ nhanh:

Cách 1Nhân thẳng bằng long long – cái bẫy tràn số

Hầu hết các bạn sẽ viết ngay thế này:

C++▶ Chạy tay từng dòng codeCách 1 (SAI): nhân thẳng bằng long long – bị tràn số khi tích vượt 2^63.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 3 2 3 5 3 3 2 4 7 8 1 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bộ "Bẫy 2^64": tích a = 3·2^64, tích b = 2^64 khác nhau, nhưng long long chỉ giữ 64 bit cuối nên cả hai thành 0 → in nhầm YES.

Với test mẫu thì đúng, nhưng long long chỉ chứa được tới khoảng $9.2 \cdot 10^{18}$ (19 chữ số), còn tích ở đây dài hàng trăm chữ số. Khi tràn, máy giữ lại 64 bit cuối của kết quả – tức là thực chất đang so sánh hai tích theo modulo $2^{64}$. Hai tích khác nhau mà bị trùng phần dư thì code trả lời sai.

Điều thú vị: phép so sánh modulo $2^{64}$ "hên" đúng ở phần lớn trường hợp, chỉ sai khi phần dư trùng nhau – và người ra đề đã cố ý tạo các bộ có hai tích đều chia hết cho $2^{64}$ (rất nhiều số chẵn), khi đó cả hai "tích" đều bằng 0! Khung chạy tay bên dưới có bộ dữ liệu "Bẫy 2^64" để em thấy tận mắt.

Kết quả chạy thật: bản C++ đúng 88/100 test (sai các test 31, 34, 39, 47, 50, 52–53, 63, 70, 87, 91, 100), chạy lâu nhất 0.005s; bản Python (nhân thẳng bằng số nguyên lớn) đúng 100/100 test, lâu nhất 0.03s.

Bài học

Đề cho số lớn mà phải nhân/cộng nhiều lần thì luôn ước lượng xem kết quả lớn cỡ nào. Ở đây $10^{9 \cdot 100} = 10^{900}$ – vượt xa mọi kiểu số nguyên của C++. Riêng Python tự dùng số nguyên lớn nên cách "nhân thẳng" vẫn đúng (cột Python ở trên).

Cách 2Phân tích thừa số nguyên tố + map

Cài đặt đúng ý tưởng ở trên. Hàm phanTich(x, d) chia thử $x$ cho $p = 2, 3, 4, \ldots$ chừng nào $p \cdot p \le x$; mỗi lần chia hết thì cộng d vào mu[p]. Phần còn lại sau vòng lặp mà lớn hơn 1 thì chắc chắn là một số nguyên tố.

C++▶ Chạy tay từng dòng codeCách 2: phân tích từng số, cộng (dãy a) / trừ (dãy b) số mũ vào map mu, cuối cùng kiểm tra mọi số mũ bằng 0.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 3 2 3 5 3 3 2 4 7 8 1 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần chỉ thử các số nguyên tố: khi tới $p = 4$ thì $x$ đã hết thừa số 2 nên $x$ không chia hết cho 4 nữa – chỉ có số nguyên tố mới chia được.
2. Điều kiện p * p <= x với $x$ đang giảm dần giúp vòng lặp dừng sớm. Mỗi số tốn không quá $\sqrt{10^9} \approx 31623$ phép chia.
3. mu.clear() ở đầu mỗi bộ test – quên dòng này là bộ sau bị "dính" số mũ của bộ trước.
4. Ta duyệt mọi phần tử của map (for(auto it : mu)): chỉ cần một số mũ khác 0 là hai tích khác nhau.

Không gian$O(\text{số thừa số khác nhau})$

Thời gian$O((n + m) \cdot \sqrt{\max a})$ mỗi bộ

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

Cách 3Giản ước từng cặp bằng UCLN

Một cách rất gọn không cần phân tích thừa số: giống như rút gọn phân số $\frac{a_1 a_2 \cdots a_n}{b_1 b_2 \cdots b_m}$. Với mỗi cặp $(a_i, b_j)$, lấy $g = \gcd(a_i, b_j)$ rồi chia cả hai cho $g$ – giá trị phân số không đổi. Làm hết mọi cặp, hai tích bằng nhau ⇔ mọi số đều về 1.

Vì sao đúng? Sau khi xét xong hàng $i$, $a_i$ nguyên tố cùng nhau với mọi $b_j$ (vì các $b_j$ sau đó chỉ bị chia nhỏ đi). Cuối cùng tích mới của $a$ và tích mới của $b$ nguyên tố cùng nhau. Nếu ban đầu hai tích bằng nhau thì sau khi cùng chia cho các $g$ chúng vẫn bằng nhau – hai số bằng nhau mà nguyên tố cùng nhau thì chỉ có thể cùng bằng 1.

C++▶ Chạy tay từng dòng codeCách 3: giản ước từng cặp (a[i], b[j]) cho UCLN, cuối cùng mọi số phải bằng 1.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 3 2 3 5 3 3 2 4 7 8 1 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n + m)$

Thời gian$O(n \cdot m \cdot \log(\max a))$ mỗi bộ

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

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Nhân thẳng	C++ (long long)	88/100	0.01s	Sai test 31, 34, 39, 47, 50, 52–53, 63, 70, 87, 91, 100 do tràn số
	Python	100/100	0.03s	Python có số nguyên lớn nên nhân thẳng vẫn đúng
2. Phân tích + map	C++	100/100	0.01s	Full điểm
	Python	100/100	0.06s	Full điểm
3. Giản ước bằng UCLN	C++	100/100	0.01s	Full điểm
	Python	100/100	0.03s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Cả Cách 2 và Cách 3 đều chạy chưa tới 0.01 giây vì $n, m \le 100$. Cách 1 chỉ sai 12 test nhưng trong phòng thi thì mất 12 điểm vì một lỗi tràn số là rất tiếc – hãy luôn ước lượng độ lớn kết quả trước khi chọn kiểu dữ liệu nhé!

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 😇