Dãy tương đương
Đề 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é).
2
2 3
10 3
2 3 5
3 3
2 4 7
8 1 5YES
NOLờ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ồ.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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ầmYES.
Ý 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 đó:
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:
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:
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.
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ố.
- 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.
- Điều kiện
p * p <= xvớ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. 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.- 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.
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.
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 |