GCD
Đề bài
GCD
Hàm băm (hash function) là một hàm số giúp chuyển dữ liệu bất kì thành một mã băm (hash code), thường có dạng một xâu có độ dài cố định. Hàm băm có ứng dụng rộng rãi trong nhiều lĩnh vực, trong đó có mật mã học (cryptography), và thậm chí là ứng dụng trong blockchain. Người ta có thể thiết kế ra một hàm băm $f$ bất kì có tính chất sau:
- Đụng độ (hash collision) có tỉ lệ rất thấp, hầu như không xảy ra. Tức $x \ne y \Rightarrow f(x) \ne f(y)$.
- Giả sử ta biết $y = f(x)$, việc tìm ra $x$ là rất khó (tốn độ phức tạp thời gian quá lớn).
- Khi đó, hàm băm có tính chất "một chiều" và có thể áp dụng được vào trong mã hóa, mật mã học.
Sau khi nghe hội thảo về những kiến thức trên, Nghĩa cảm thấy rất thú vị và muốn áp dụng ngay. Cậu muốn mã hóa hai dãy số nguyên dương $a, b$ có kích thước lần lượt là $n, m$ phần tử. Cậu định nghĩa:
- $A = a_1 \cdot a_2 \cdots a_n$ (tích các số trong dãy $a$)
- $B = b_1 \cdot b_2 \cdots b_m$ (tích các số trong dãy $b$)
- $f(a, b)$ $= \gcd(A, B) \bmod (10^9 + 7)$, tức là ước chung lớn nhất của tích hai dãy, chia lấy dư cho $(10^9 + 7)$ vì số rất lớn.
Nghĩa nhận thấy hàm $f$ trên có tính chất "một chiều" như đã nêu trên, nhưng do cậu không giỏi lắm về tin học nên chưa thiết kế được thuật toán hiệu quả để tính $f$. Nghĩa cần được các bạn thí sinh THT trợ giúp!
Yêu cầu: Cho hai dãy $a, b$, hãy tính và in ra $f(a, b)$.
Input:
- Dòng thứ nhất chứa hai số nguyên $n, m$ $(1 \le n, m \le 5 \cdot 10^5)$ – lần lượt là kích thước hai dãy.
- Dòng thứ hai chứa $n$ số nguyên $a_i$ $(1 \le a_i \le 10^7)$.
- Dòng thứ ba chứa $m$ số nguyên $b_i$ $(1 \le b_i \le 10^7)$.
Output: Gồm một dòng duy nhất chứa $f(a, b)$.
Scoring:
- Subtask 1 (30% số điểm): $n, m \le 14$ và $a_i, b_i \le 20$.
- Subtask 2 (30% số điểm): $n = 1$.
- Subtask 3 (20% số điểm): $n, m, a_i, b_i \le 10^5$.
- Subtask 4 (20% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 2 giây, bộ nhớ: 256 MB.
4 4
5 3 2 18
6 7 10 3180Lời mở đầu
Ở ví dụ: $A = 5 \cdot 3 \cdot 2 \cdot 18$ $= 540$ $= 2^2 \cdot 3^3 \cdot 5$ và $B = 6 \cdot 7 \cdot 10 \cdot 3$ $= 1260$ $= 2^2 \cdot 3^2 \cdot 5 \cdot 7$. Ước chung lớn nhất lấy mỗi số nguyên tố với số mũ nhỏ hơn: $\gcd = 2^2 \cdot 3^2 \cdot 5 = 180$.
Đề bài kể chuyện hàm băm khá dài nhưng thực chất là một bài số học: tích $A, B$ có thể có hàng triệu chữ số nên không thể tính $\gcd$ trực tiếp. Chìa khoá là phân tích từng số ra thừa số nguyên tố và đếm số mũ bằng map. Mình sẽ đi qua cả 4 subtask, mỗi subtask một cách, và chạy thật trên bộ test.
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ì?
Bộ test có 100 test, chia đúng 4 nhóm theo 4 subtask:
| Test | n | m | Giá trị $a_i, b_i$ |
|---|---|---|---|
| 1–30 | 2 … 13 | 1 … 12 | 1 … 20 |
| 31–60 | 1 | 100.000 | 100 … 99.999 |
| 61–80 | 100.000 | 100.000 | 100 … 99.999 |
| 81–100 | 500.000 | 500.000 | 100.000 … 9.999.998 |
- Subtask trong đề khớp với bộ test.
- Ở 30 test của subtask 2 ($n = 1$), tích $B$ luôn chia hết cho $a_1$ nên đáp án luôn đúng bằng $a_1$. Đây là một điểm "yếu" của bộ test: có những code sai nhưng vẫn ăn trọn subtask này (xem cách 1 bên dưới).
- Ở subtask 4, các số đều từ $10^5$ tới $10^7$, mỗi dãy $5 \cdot 10^5$ số.
Số test đúng của từng cách (chạy thật, giới hạn 2 giây):
| Subtask | Đề ghi | Test | Cách 1 (nhân thẳng) | Cách 2 (n = 1) | Cách 3 (chia thử + map) | Cách 4 (sàng + map) |
|---|---|---|---|---|---|---|
| 1 (30%) | $n, m \le 14$, $a_i, b_i \le 20$ | 1–30 | 30/30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $n = 1$ | 31–60 | 30/30 | 30/30 | 30/30 | 30/30 |
| 3 (20%) | $n, m, a_i, b_i \le 10^5$ | 61–80 | 0/20 | 0/20 | 20/20 | 20/20 |
| 4 (20%) | không thêm | 81–100 | 0/20 | 0/20 | 20/20 | 20/20 |
Ý tưởnggcd = lấy số mũ nhỏ hơn của từng số nguyên tố
Nếu $A = \prod p^{\alpha_p}$ và $B = \prod p^{\beta_p}$ thì
Một cách nhìn dễ hình dung hơn là ghép cặp: bỏ tất cả thừa số nguyên tố của dãy $a$ vào một "túi" (ví dụ $540$ cho túi $\{2, 2, 3, 3, 3, 5\}$). Sau đó lần lượt lấy từng thừa số nguyên tố $p$ của dãy $b$: nếu trong túi còn $p$ thì lấy ra một quả và nhân $p$ vào đáp án. Số cặp ghép được của mỗi $p$ đúng bằng $\min(\alpha_p, \beta_p)$. "Túi" chính là một map<int, int> đếm số lần mỗi thừa số còn lại.
Em nhập hai dãy rồi bấm Tiếp để xem quá trình bỏ vào túi và ghép cặp:
Việc còn lại là phân tích nhanh $10^6$ số, mỗi số tới $10^7$, ra thừa số nguyên tố: chia thử tới $\sqrt{x}$ (cách 3) hoặc sàng trước ước nguyên tố nhỏ nhất (cách 4).
Cách 1Nhân thẳng – Subtask 1
Với $n, m \le 14$ và các số $\le 20$: $A, B \le 20^{14} \approx 1{,}6 \cdot 10^{18}$, vừa trong long long. Cứ nhân thẳng rồi dùng hàm __gcd có sẵn (thuật toán Euclid), nhớ lấy dư cho $10^9 + 7$ ở cuối.
Kết quả chạy thật: Bản C++ đúng 60/100 test, sai ở test 61–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 31/40 test (mình chỉ chạy test 1–40), quá thời gian ở test 31–34, 36–40; test đúng chạy lâu nhất 1.91s.
long long (thực chất là lấy dư cho $2^{64}$) làm $B$ thành $0$ – và $\gcd(a_1, 0) = a_1$ đúng bằng đáp án của mọi test nhóm này! Code sai mà vẫn ăn 30% điểm. Các bạn đừng học theo nhé, gặp bộ test chặt hơn là mất điểm ngay.Cách 2Khi n = 1: rút dần phần chung – Subtask 1, 2
Khi $n = 1$, ta cần $\gcd(a_1, b_1 b_2 \cdots b_m)$. Giữ $g$ = "phần của $a_1$ chưa được ghép". Với mỗi $b_i$: phần chung là $d = \gcd(g, b_i)$, ta nhân $d$ vào đáp án và bỏ nó khỏi $g$ ($g = g / d$). Đây chính là ý tưởng ghép cặp, nhưng làm bằng gcd nên không cần phân tích thừa số. Code vẫn giữ lại phần nhân thẳng cho subtask 1.
- Vì sao đúng? Phần chung của $g$ và $b_i$ chắc chắn nằm trong $\gcd(a_1, B)$; sau khi bỏ $d$ ra khỏi $g$, phần còn lại của $g$ chỉ có thể ghép với các $b$ phía sau. Tích các $d$ luôn là ước của $a_1$ nên không vượt quá $10^7$.
- Mỗi bước chỉ một lần
__gcd– $O(\log)$.
Kết quả chạy thật: Bản C++ đúng 60/100 test, sai ở test 61–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 60/80 test (mình chỉ chạy test 1–80), quá thời gian ở test 61–80; test đúng chạy lâu nhất 0.07s. Ăn trọn subtask 1, 2 (60% điểm) – lần này là đúng thật chứ không nhờ may mắn.
Cách 3Chia thử + map số mũ – Subtask 1, 2, 3
Làm đúng theo công thức: phân tích từng số bằng cách chia thử $p = 2, 3, 4, \ldots$ chừng nào $p^2 \le x$, cộng số mũ vào map ca (cho dãy $a$) và cb (cho dãy $b$). Cuối cùng duyệt ca, với mỗi $p$ có trong cả hai thì nhân $p^{\min}$ vào đáp án bằng lũy thừa nhanh.
- Sau vòng chia thử, 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ố mũ tổng có thể tới $5 \cdot 10^5 \cdot 23$ nên để kiểu
long longcho chắc, và dùng hàmluyThua(lũy thừa nhanh, nhân bình phương) để tính $p^e \bmod (10^9+7)$. - Vòng
for(auto [p, e] : ca)dùng cú pháp C++17 để lấy luôn khoá và giá trị.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 1.54s. Bản Python đúng 80/100 test, quá thời gian ở test 81–100; test đúng chạy lâu nhất 0.98s. Với số tới $10^7$, mỗi số có thể phải chia thử tới khoảng 3162 lần (khi nó là số nguyên tố). Trên bộ test này đa số các số có ước nhỏ nên vẫn kịp, nhưng thời gian khá sát giới hạn 2 giây – sang máy chấm chậm hơn là có thể quá giờ.
Cách 4Sàng ước nguyên tố nhỏ nhất + map ghép cặp – Full điểm
Sàng trước spf[x] (ước nguyên tố nhỏ nhất) cho mọi $x \le 10^7$, khi đó phân tích một số chỉ mất tối đa khoảng 23 phép chia ($2^{23} > 10^7$). Phần đếm dùng ý tưởng ghép cặp: map cnt là túi thừa số của dãy $a$; với mỗi thừa số $p$ của dãy $b$, nếu túi còn $p$ thì lấy ra và nhân $p$ vào đáp án.
- Sàng tuyến tính: với mỗi $i$, chỉ gạch các số $i \cdot p$ với $p$ nguyên tố $\le$
spf[i], nên mỗi hợp số bị gạch đúng 1 lần (bởi ước nguyên tố nhỏ nhất của nó). Tổng thời gian $O(10^7)$. Mảngspfkiểuinttốn 40 MB – vẫn trong giới hạn 256 MB. - Ghép cặp giúp không cần map thứ hai và không cần hàm lũy thừa: mỗi lần ghép được chỉ là một phép nhân.
cnt.find(p)thay vìcnt[p]để không vô tình thêm khoá mới (giá trị 0) vàomap.- Bản Python sàng bằng các phép gán lát cắt (slice) trên
arrayđể chạy ở tốc độ C, rồi đếm số mũ bằngdictnhư cách 3.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 1.08s. Bản Python đúng 85/100 test, quá thời gian ở test 84–90, 92–99; test đúng chạy lâu nhất 1.98s.
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 + __gcd | C++ | 60/100 | 0.01s | Sai test 61–100 (tràn số; test 31–60 đúng nhờ may mắn) |
| Python | 31/40 | > 2s | Mình chỉ chạy test 1–40; quá thời gian test 31–34, 36–40 | |
| 2. Riêng $n = 1$: rút gcd dần | C++ | 60/100 | 0.01s | Sai test 61–100 |
| Python | 60/80 | > 2s | Mình chỉ chạy test 1–80; quá thời gian test 61–80 | |
3. Chia thử + map số mũ | C++ | 100/100 | 1.54s | Full điểm – nhưng khá sát giới hạn |
| Python | 80/100 | > 2s | Quá thời gian test 81–100 | |
4. Sàng spf + map ghép cặp | C++ | 100/100 | 1.08s | Full điểm |
| Python | 85/100 | > 2s | Quá thời gian test 84–90, 92–99 | |
4'. Như cách 4, thay map bằng mảng | C++ | 100/100 | 0.65s | Full điểm |
map; nếu thay map bằng mảng đếm int cnt[10^7 + 1] (thêm 40 MB) thì chỉ còn 0.65 giây (dòng 4' trong bảng). Với giới hạn 2 giây thì bản map vẫn qua thoải mái và đúng tinh thần chương Map/Set.
Nhận xét
Đăng nhận xét