Cặp số may mắn
Đề bài
Một cặp số nguyên dương $(x, y)$ được gọi là cặp số may mắn nếu tồn tại số nguyên dương $k$ sao cho $x^k + y^k$ chia hết cho $x \cdot y$.
Ví dụ:
- $(2, 4)$ là cặp may mắn vì $2^3 + 4^3 = 8 + 64 = 72$ chia hết cho $2 \cdot 4 = 8$;
- $(3, 3)$ là cặp may mắn vì $3^2 + 3^2 = 9 + 9 = 18$ chia hết cho $3 \cdot 3 = 9$;
- $(1, 2)$ không phải là cặp may mắn vì $1^k + 2^k$ luôn lẻ với mọi $k > 0$ nên không thể chia hết cho $1 \cdot 2 = 2$.
Cho một mảng $a$ chứa $n$ số nguyên dương, nhiệm vụ của bạn là đếm số cặp $(i, j)$ sao cho $i < j$ và $(a_i, a_j)$ là cặp may mắn.
Dữ liệu vào:
- Dòng đầu tiên là số nguyên dương $n$ $(n \le 3 \cdot 10^5)$ là độ dài của mảng.
- $n$ dòng tiếp theo mỗi dòng ghi một số nguyên dương $a_1, a_2, a_3, \ldots, a_n$ với $a_i \le 10^6$.
Dữ liệu ra: viết một số nguyên duy nhất là số cặp may mắn trong mảng $a$.
6
1
2
3
4
5
61Lời mở đầu
Trong ví dụ, mảng là $1, 2, 3, 4, 5, 6$ và chỉ có đúng một cặp may mắn là $(2, 4)$. Đề bài cho định nghĩa với "tồn tại số mũ $k$" – nghe thì phải thử vô hạn số $k$, nhưng chỉ cần một chút số học là định nghĩa này biến thành một điều kiện rất đơn giản, và bài toán trở thành bài đếm cặp bằng map quen thuộc. Mình sẽ đi từ cách thử trực tiếp theo định nghĩa, tới nhận xét toán học, rồi tới lời giải full điểm.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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ì?
| Test | n | max ai | Đáp án max | C1 | C2 | C3 |
|---|---|---|---|---|---|---|
| 1–10 | 1 – 18 | 98 | 12 | 10/10 | 10/10 | 10/10 |
| 11–20 | 100 | 988.458 | 190 | 10/10 | 10/10 | 10/10 |
| 21–30 | 1.000 | 999.978 | 15.174 | 10/10 | 10/10 | 10/10 |
| 31–40 | 10.000 | 999.924 | 1.206.040 | 0/10 | 10/10 | 10/10 |
| 41–50 | 100.000 | 999.992 | 116.361.650 | 0/10 | 0/10 | 10/10 |
| 51–100 | 300.000 | 999.999 | 1.040.427.633 | 0/50 | 0/50 | 50/50 |
Bộ test có 100 test, đề không ghi subtask nhưng $n$ tăng dần theo từng nhóm 10 test rất rõ ràng ($n \le 18$, 100, 1000, $10^4$, $10^5$), riêng 50 test cuối đều có $n = 3 \cdot 10^5$. Ba cột cuối (C1, C2, C3 = cách 1, 2, 3 bản C++) là số test chạy đúng trong 1 giây (mình đo thời gian CPU). Vài điều đáng chú ý:
- Đáp án lên tới khoảng $1.04 \cdot 10^9$ – vẫn vừa
intnhưng sát nút, và về lý thuyết có thể tới $\frac{n(n-1)}{2} \approx 4.5 \cdot 10^{10}$, nên bắt buộc dùnglong long. - Dữ liệu có rất nhiều số trùng nhau và rất nhiều số 1: ví dụ test 60 có 39.165 số 1, chỉ 89.021 giá trị khác nhau trên 300.000 số. Cặp (1, 1) luôn may mắn vì $1 + 1 = 2$ chia hết cho $1$.
Cách 1Thử trực tiếp theo định nghĩa
Với mỗi cặp $(a_i, a_j)$, ta thử $k = 1, 2, 3, \ldots$ và kiểm tra $x^k + y^k$ có chia hết cho $m = x \cdot y$ không. Không cần tính $x^k$ thật (quá lớn), chỉ cần giữ phần dư $p_x = x^k \bmod m$, mỗi bước nhân thêm $x$ rồi lấy dư.
Câu hỏi là: thử tới $k$ bằng bao nhiêu thì dừng? Ở phần nhận xét bên dưới mình sẽ chứng minh nếu có $k$ thoả mãn thì $k = 40$ chắc chắn cũng thoả mãn (vì $a_i \le 10^6 < 2^{20}$). Vậy thử $k$ từ 1 đến 40 là đủ.
- $m = x \cdot y$ có thể tới $10^{12}$, nên
px * xcó thể tới $10^{18}$; mình ép sang__int128trước khi nhân cho chắc chắn không tràn số. - Python có sẵn
pow(x, k, m)tính $x^k \bmod m$ nhanh nên viết gọn hơn.
Kết quả chạy thật: bản C++ đúng 30/100 test (thời gian CPU lớn nhất trong các test đúng: 0.29 giây); từ test 31 ($n = 10.000$, khoảng $5 \cdot 10^7$ cặp × 40 lần thử) bắt đầu quá thời gian. Bản Python đúng 20/100 test.
Nhận xétKhi nào (x, y) là cặp may mắn?
Thử vài cặp bằng widget dưới đây để "cảm" quy luật trước nhé. Em nhập $x, y$ rồi bấm Tiếp, máy sẽ thử lần lượt $k = 1, 2, \ldots$ và tính $(x^k + y^k) \bmod xy$:
Để ý cột "ước nguyên tố": các cặp may mắn như $(2, 4)$, $(6, 12)$, $(12, 18)$ có cùng tập ước nguyên tố; còn $(2, 6)$ thì 6 có thêm ước 3 mà 2 không có – thử mãi không chia hết. Đó chính là điều kiện cần tìm:
Chiều thuận: giả sử có số nguyên tố $q$ chia hết $x$ mà không chia hết $y$. Nếu $xy \mid x^k + y^k$ thì $q \mid x^k + y^k$, mà $q \mid x^k$ nên $q \mid y^k$, suy ra $q \mid y$ – vô lý. Vậy mọi ước nguyên tố của $x$ đều là ước của $y$, và ngược lại.
Chiều đảo: giả sử $x, y$ cùng tập ước nguyên tố. Xét một ước nguyên tố $q$ bất kỳ, $x$ chứa $q^{\alpha}$ và $y$ chứa $q^{\beta}$ với $\alpha, \beta \ge 1$. Khi đó $x^k + y^k$ chia hết cho $q^{k \cdot \min(\alpha, \beta)}$, mà $xy$ chỉ chứa $q^{\alpha + \beta}$. Chọn $k \ge \alpha + \beta$ thì $k \cdot \min(\alpha, \beta)$ $\ge k$ $\ge \alpha + \beta$, đúng với mọi $q$. Vì $a_i \le 10^6 < 2^{20}$ nên $\alpha, \beta \le 19$, chọn $k = 40$ là luôn được – đây chính là lý do cách 1 chỉ cần thử tới 40.
Bài toán giờ thành: đếm số cặp $i < j$ có $\text{rad}(a_i) = \text{rad}(a_j)$.
Cách 2Tính rad rồi so từng cặp
Tính $\text{rad}(a_i)$ cho từng số bằng cách chia thử tới $\sqrt{a_i}$, rồi đếm các cặp có rad bằng nhau bằng 2 vòng lặp lồng nhau. Mỗi cặp giờ chỉ tốn 1 phép so sánh thay vì 40 lần nhân chia.
Kết quả chạy thật: bản C++ đúng 40/100 test (thời gian CPU lớn nhất trong các test đúng: 0.07 giây); từ test 41 ($n = 100.000$, khoảng $5 \cdot 10^9$ cặp) thì quá thời gian. Bản Python đúng 30/100 test.
Ý tưởngGom nhóm theo rad bằng map
Các số có cùng rad tạo thành một nhóm, hai số bất kỳ trong cùng nhóm là một cặp may mắn. Nhóm có $c$ phần tử cho $\frac{c(c-1)}{2}$ cặp. Ta dùng map<int, int> cnt đếm số phần tử của mỗi nhóm. Mẹo hay dùng: duyệt từng số, trước khi tăng cnt[r] thì cộng cnt[r] vào đáp án – đó chính là số cặp mà số hiện tại tạo với các số đứng trước nó cùng nhóm (tổng lại đúng bằng $0 + 1 + \cdots + (c - 1) = \frac{c(c-1)}{2}$).
Để tính rad nhanh cho $3 \cdot 10^5$ số, mình sàng trước mảng spf[x] = ước nguyên tố nhỏ nhất của $x$ với mọi $x \le 10^6$. Khi đó tách thừa số chỉ cần lặp: lấy $p = \text{spf}[x]$, chia hết $p$ ra khỏi $x$, lặp lại – mỗi số tốn $O(\log a_i)$ bước.
Em nhập mảng rồi bấm Tiếp để xem từng số được tính rad và cho vào "nhóm" trong map:
100%Cách 3: sàng spf + map đếm
- Vòng sàng: với mỗi $i$ chưa có
spf(tức $i$ nguyên tố), gánspf[j] = icho các bội $j$ chưa được gán. Tổng số bước khoảng $M \ln \ln M$, rất nhanh. - Biến
ansphải làlong long: có test đáp án vượt $10^9$. - Bản Python mình phải tối ưu thêm cho kịp 1 giây: sàng
spfbằng phép gán lát cắtspf[p*p::p] = [p] * ...(chạy ở tốc độ của C) với $p$ duyệt giảm dần để số nguyên tố nhỏ nhất được gán sau cùng; rồi chỉ tách thừa số cho các giá trị khác nhau (khoảng 89 nghìn thay vì 300 nghìn số) và cộng $\frac{c(c-1)}{2}$ cho mỗi nhóm. Bản đầu tiên mình viết bằng vòngforthường thì quá thời gian 4/100 test.
Kết quả chạy thật: bản C++ đúng 100/100 test (thời gian CPU lớn nhất trong các test đúng: 0.21 giây). Bản Python đúng 100/100 test.
map): C++ 100/100 (CPU tối đa 0.21 s), Python 100/100.
Nhận xét
Đăng nhận xét