Đan lục bình (Đề tự luyện HSG Tin 12 – Bài 1)
Đề bài
Đan lục bình. Thầy Sơn có $N$ bó lục bình, bó thứ $i$ có $a_i$ sợi. Với hai bó $i < j$, thầy chia toàn bộ sợi của hai bó thành các lọn có cùng số sợi (mỗi lọn lấy từ một bó, không bó nào thừa sợi), mỗi lọn nhiều sợi nhất có thể; số sợi mỗi lọn gọi là độ dày của cặp. Có $Q$ đơn hàng, đơn thứ $k$ cho đoạn $[L_k, R_k]$: đếm số cặp bó $(i, j)$, $i < j$, có độ dày thuộc $[L_k, R_k]$.
Dữ liệu vào: dòng đầu $N, Q$ ($1 \le N \le 3 \cdot 10^5$, $1 \le Q \le 10^5$); dòng hai gồm $a_1, \ldots, a_N$ ($1 \le a_i \le 10^6$); $Q$ dòng sau mỗi dòng hai số $L_k \le R_k$ ($1 \le L_k \le R_k \le 10^6$).
Kết quả: $Q$ dòng, dòng thứ $k$ là đáp án của đơn thứ $k$.
- Subtask 1 (20%): $N \le 2000$.
- Subtask 2 (30%): $a_i \le 3000$.
- Subtask 3 (50%): không có ràng buộc gì thêm.
5 3
6 4 9 10 15
2 3
3 1000000
4 106
4
1Độ dày của cặp chính là ƯCLN hai số sợi. 10 cặp có độ dày: 1 (3 cặp: (4,9), (4,15), (9,10)), 2 (3 cặp: (6,4), (6,10), (4,10)), 3 (3 cặp: (6,9), (6,15), (9,15)), 5 (cặp (10,15)). Đơn [2,3] → 3 + 3 = 6; đơn [3, 106] → 3 + 1 = 4; đơn [4, 10] → 1.
Bạ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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Đan lục bìnhLời mở đầu
Trước hết các bạn "dịch" đề sang ngôn ngữ toán. Một lọn có $t$ sợi dùng được cho cả hai bó khi và chỉ khi $t$ chia hết $a_i$ và chia hết $a_j$, tức $t$ là một ước chung. Lọn nhiều sợi nhất có thể nghĩa là lấy ước chung lớn nhất. Vậy:
$$\text{độ dày}(i, j) = \gcd(a_i, a_j).$$
Hình 1. Bó 6 sợi và bó 9 sợi: lọn lớn nhất dùng được cho cả hai là 3 sợi = ƯCLN(6, 9).
Bài toán trở thành: với mỗi đoạn $[L, R]$, đếm số cặp $i < j$ có $L \le \gcd(a_i, a_j) \le R$. Có hai nhận xét quan trọng:
- Tách phần "đếm" khỏi phần "trả lời". Nếu ta biết $g[d]$ = số cặp có ƯCLN đúng bằng $d$ cho mọi $d$ từ $1$ đến $10^6$, thì với mảng cộng dồn $P[x] = g[1] + \ldots + g[x]$, mỗi đơn trả lời ngay bằng $P[R] - P[L-1]$ trong $O(1)$. Toàn bộ độ khó nằm ở việc tính mảng $g$.
- Đáp án rất lớn. Số cặp tối đa là $\binom{3 \cdot 10^5}{2} \approx 4{,}5 \cdot 10^{10}$, vượt xa giới hạn của
int(khoảng $2{,}1 \cdot 10^9$). Phải dùnglong long.
Các cách dưới đây chỉ khác nhau ở chỗ tính mảng $g$ nhanh đến đâu.
Cách 1Duyệt mọi cặp – O(N² log A) · 20%
Cách tự nhiên nhất: duyệt mọi cặp $i < j$, tính $\gcd(a_i, a_j)$ rồi tăng f[gcd] lên 1. Xong thì cộng dồn mảng f và trả lời từng đơn bằng hiệu hai phần tử.
Với $N \le 2000$ có khoảng $2 \cdot 10^6$ cặp, mỗi lần tính ƯCLN tốn $O(\log A)$ – chạy rất nhanh. Nhưng với $N = 3 \cdot 10^5$ có tới $4{,}5 \cdot 10^{10}$ cặp thì không thể chạy kịp.
#include <bits/stdc++.h>
using namespace std;
const int V = 1000000;
long long f[V + 1];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
f[__gcd(a[i], a[j])]++;
for (int d = 1; d <= V; d++) f[d] += f[d - 1];
while (q--) {
int L, R;
cin >> L >> R;
cout << f[R] - f[L - 1] << "\n";
}
return 0;
}import sys
from math import gcd
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
f = [0] * 1000001
for i in range(n):
x = a[i]
for j in range(i + 1, n):
f[gcd(x, a[j])] += 1
f = list(accumulate(f))
out = []
p = 2 + n
for _ in range(q):
L = int(data[p]); R = int(data[p + 1]); p += 2
out.append(f[R] - f[L - 1])
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 2Gộp các bó cùng số sợi – O(D² log A) · 50%
Ở subtask 2, $N$ có thể lên tới $3 \cdot 10^5$ nhưng $a_i \le 3000$, nên có rất nhiều bó trùng số sợi. Gọi $D$ là số giá trị khác nhau ($D \le 3000$) và cnt[x] là số bó có đúng $x$ sợi. Thay vì xét từng cặp bó, ta xét từng cặp giá trị:
- Hai giá trị khác nhau $x < y$: có
cnt[x] · cnt[y]cặp bó, tất cả cùng độ dày $\gcd(x, y)$. - Hai bó cùng giá trị $x$: có $\binom{cnt[x]}{2}$ cặp, độ dày là $\gcd(x, x) = x$. Đây là chỗ hay bị quên!
Số cặp giá trị chỉ khoảng $D^2/2 \approx 4{,}5 \cdot 10^6$. Cách này vẫn đúng cho subtask 1 (khi đó $D \le N \le 2000$). Nhưng ở subtask 3 có thể có tới $3 \cdot 10^5$ giá trị khác nhau, $D^2$ lại quá lớn.
#include <bits/stdc++.h>
using namespace std;
const int V = 1000000;
long long cnt[V + 1], f[V + 1];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
int x; cin >> x;
cnt[x]++;
}
vector<int> v; // cac gia tri khac nhau
for (int x = 1; x <= V; x++)
if (cnt[x] > 0) v.push_back(x);
int m = v.size();
for (int i = 0; i < m; i++) {
long long c = cnt[v[i]];
f[v[i]] += c * (c - 1) / 2; // hai bo cung so soi
for (int j = i + 1; j < m; j++)
f[__gcd(v[i], v[j])] += c * cnt[v[j]];
}
for (int d = 1; d <= V; d++) f[d] += f[d - 1];
while (q--) {
int L, R;
cin >> L >> R;
cout << f[R] - f[L - 1] << "\n";
}
return 0;
}import sys
from math import gcd
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
cnt = {}
for x in map(int, data[2:2 + n]):
cnt[x] = cnt.get(x, 0) + 1
v = sorted(cnt) # cac gia tri khac nhau
f = [0] * 1000001
for i in range(len(v)):
x = v[i]; c = cnt[x]
f[x] += c * (c - 1) // 2 # hai bo cung so soi
for j in range(i + 1, len(v)):
y = v[j]
f[gcd(x, y)] += c * cnt[y]
f = list(accumulate(f))
out = []
p = 2 + n
for _ in range(q):
L = int(data[p]); R = int(data[p + 1]); p += 2
out.append(f[R] - f[L - 1])
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 3Sàng bội số + trừ lùi – O(V log V) · 100%
Đếm trực tiếp "ƯCLN đúng bằng $d$" thì khó. Nhưng đếm "ƯCLN chia hết cho $d$" lại dễ:
$$d \mid \gcd(a_i, a_j) \iff d \mid a_i \ \text{và}\ d \mid a_j.$$
Gọi $c[d]$ là số bó có số sợi chia hết cho $d$. Chọn hai bó bất kì trong $c[d]$ bó đó là được một cặp có ƯCLN chia hết cho $d$, nên có đúng $\binom{c[d]}{2}$ cặp như vậy. Tính $c[d]$ bằng sàng bội số: $c[d] = cnt[d] + cnt[2d] + cnt[3d] + \ldots$
Các cặp có ƯCLN chia hết cho $d$ thì có ƯCLN đúng bằng một trong các số $d, 2d, 3d, \ldots$ Do đó
$$\binom{c[d]}{2} = g[d] + g[2d] + g[3d] + \cdots \quad\Longrightarrow\quad g[d] = \binom{c[d]}{2} - \sum_{k \ge 2} g[k \cdot d].$$
Nếu ta đi $d$ từ lớn xuống nhỏ, khi tới $d$ thì mọi $g[2d], g[3d], \ldots$ đều đã tính xong. Mình gọi đây là kĩ thuật "trừ lùi".
Hình 2. Với dãy $a = 6, 4, 9, 12, 3$: 4 bó (3, 6, 9, 12) chia hết cho 3 nên có 6 cặp có ƯCLN chia hết cho 3; bỏ đi 1 cặp có ƯCLN = 6 thì còn 5 cặp có ƯCLN đúng bằng 3.
Chạy tay với dãy $a = 6, 4, 9, 12, 3$ (mình không dùng ví dụ của đề vì ở đó mọi độ dày đều là 1 hoặc số nguyên tố, khó thấy tác dụng của trừ lùi; $M = 12$; các $d$ có $c[d] \le 1$ đều cho $g[d] = 0$):
| d | Các bó chia hết d | c[d] | C(c[d], 2) | Trừ | g[d] |
|---|---|---|---|---|---|
| 12 | 12 | 1 | 0 | – | 0 |
| 6 | 6, 12 | 2 | 1 | g[12] = 0 | 1 |
| 4 | 4, 12 | 2 | 1 | g[8] + g[12] = 0 | 1 |
| 3 | 6, 9, 12, 3 | 4 | 6 | g[6] + g[9] + g[12] = 1 | 5 |
| 2 | 6, 4, 12 | 3 | 3 | g[4] + g[6] + g[8] + g[10] + g[12] = 2 | 1 |
| 1 | tất cả | 5 | 10 | g[2] + … + g[12] = 8 | 2 |
Cộng dồn: $P[1] = 2$, $P[2] = 3$, $P[3] = 8$, $P[4] = P[5] = 9$, $P[6] = \ldots = P[10^6] = 10$. Đơn $[2, 4]$: $P[4] - P[1] = 7$ ✓.
Độ phức tạp. Với mỗi $d$ ta duyệt các bội $d, 2d, \ldots \le M$, mất $M/d$ bước. Tổng là $M(1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1M) \approx M \ln M \approx 1{,}4 \cdot 10^7$ với $M = 10^6$ (chuỗi điều hoà). Trong code mình gộp luôn việc tính $c[d]$ và tổng trừ vào cùng một vòng lặp qua các bội.
Các bạn thử tự nhập dãy số sợi và xem bảng $c[d]$, $g[d]$ được điền từ phải sang trái:
- Lấy luôn $\binom{c[d]}{2}$ làm đáp án cho $d$ (quên trừ lùi) – đó là số cặp có ƯCLN chia hết cho $d$, không phải bằng $d$. Ví dụ của đề cố ý có mọi độ dày đều là $1$ hoặc số nguyên tố, nên cách sai này vẫn ra đúng cả ba đơn của ví dụ – đừng vội tin!
- Tính $c \cdot (c-1)/2$ bằng
int: với $c = 3 \cdot 10^5$ thì $c(c-1) \approx 9 \cdot 10^{10}$ bị tràn số. - Trả lời $P[R] - P[L]$ thay vì $P[R] - P[L-1]$ (mất các cặp có độ dày đúng bằng $L$).
Bản Python dùng lát cắt cnt[d::d] và f[2*d:M+1:d] với sum để cộng các bội ở tốc độ của C, nên chạy nhanh hơn nhiều so với vòng for lồng nhau.
#include <bits/stdc++.h>
using namespace std;
const int V = 1000000;
int cnt[V + 1];
long long f[V + 1];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q, M = 0;
cin >> n >> q;
for (int i = 0; i < n; i++) {
int x; cin >> x;
cnt[x]++;
M = max(M, x);
}
for (int d = M; d >= 1; d--) {
long long c = 0, bad = 0;
for (int k = d; k <= M; k += d) {
c += cnt[k];
if (k > d) bad += f[k];
}
f[d] = c * (c - 1) / 2 - bad;
}
for (int d = 1; d <= V; d++) f[d] += f[d - 1];
while (q--) {
int L, R;
cin >> L >> R;
cout << f[R] - f[L - 1] << "\n";
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
V = 1000000
a = list(map(int, data[2:2 + n]))
M = max(a)
cnt = [0] * (M + 1)
for x in a:
cnt[x] += 1
f = [0] * (V + 1)
for d in range(M, 0, -1):
c = sum(cnt[d::d])
f[d] = c * (c - 1) // 2 - sum(f[2 * d:M + 1:d])
f = list(accumulate(f))
out = []
p = 2 + n
for _ in range(q):
L = int(data[p]); R = int(data[p + 1]); p += 2
out.append(f[R] - f[L - 1])
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 29 test: 10 test subtask 1 ($N \le 2000$), 9 test subtask 2 ($N \approx 3 \cdot 10^5$, $a_i \le 3000$, có test toàn số 1 và test toàn bộ bằng nhau cho đáp án $\approx 4{,}5 \cdot 10^{10}$), 10 test subtask 3 ($N \approx 3 \cdot 10^5$, mỗi test có ít nhất $10^5$ giá trị khác nhau). Mỗi test có $10^5$ đơn hàng.
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (50%) | Điểm |
|---|---|---|---|---|
| Cách 1 – duyệt mọi cặp O(N²) | Đúng | TLE | TLE | 20 |
| Cách 2 – gộp giá trị trùng O(D²) | Đúng | Đúng | TLE | 50 |
| Cách 3 – sàng bội + trừ lùi | Đúng | Đúng | Đúng | 100 |
Sai 1 – dùng int cho số cặp | Đúng | WA | WA | 20 |
| Sai 2 – quên trừ lùi (đếm cặp có ƯCLN chia hết d) | 1/10 test | 1/9 test | WA | ≈ 5 |
| Sai 3 – lấy f[R] − f[L] (lệch chỉ số) | 1/10 test | WA | WA | 2 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 (dưới 0,3 giây) và quá 3 giây ở mọi test còn lại; Cách 2 đúng hết subtask 1, 2 và quá 3 giây ở mọi test subtask 3; Cách 3 đúng 29/29 test, test lâu nhất khoảng 0,45 giây. Hai test mà "Sai 2", "Sai 3" ăn may là các test đặc biệt (một bó duy nhất, hoặc toàn bộ ƯCLN đều bằng 1). Cách duyệt ước từng $a_i$ trong $O(\sqrt{a_i})$ rồi trừ lùi vẫn đúng nhưng chạy khoảng 0,9 giây – rất sát giới hạn, các bạn nên dùng sàng bội.
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 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét