Ước Chung Lớn Nhất (GCD – Bài 4, đề HSG)
Đề bài
Bài 4. ƯỚC CHUNG LỚN NHẤT (2.5 điểm)
Ước chung lớn nhất của một tập $A$ các số nguyên dương là số nguyên dương $d$ lớn nhất sao cho $d$ là ước của mọi số trong tập $A$.
Yêu cầu: Cho dãy gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ và số $k$ $(2 \le k \le n)$. Hãy tìm một đoạn liên tiếp các phần tử $a_i, a_{i+1}, \dots, a_{i+k-1}$ sao cho ước chung lớn nhất của các phần tử này là lớn nhất.
Dữ liệu: Vào từ file văn bản GCD.INP
- Dòng đầu tiên chứa hai số nguyên $n$ và $k$ $(2 \le k \le n \le 10^5)$.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{18})$.
Kết quả: Ghi ra file văn bản GCD.OUT một số nguyên là kết quả của bài toán.
Ràng buộc: 50% số test đầu tiên tương ứng với $n \le 1000$.
Lưu ý: trên hệ thống chấm online, chương trình đọc dữ liệu từ bàn phím (stdin) và ghi ra màn hình (stdout), không dùng file.
10 3
2 6 4 3 18 12 24 8 7 56Giải thích: Trong tất cả các bộ 3 phần tử liên tiếp của dãy $(2, 6, 4, 3, 18, 12, 24, 8, 7, 5)$ thì ba phần tử liên tiếp $(18, 12, 24)$ có ước chung lớn nhất bằng $6$ là lớn nhất.
Lời mở đầu
Bài này là bài cuối cùng (cũng là bài khó nhất) trong đề thi tuyển sinh đầu vào lớp 10 chuyên Tin của trường Phổ Thông Năng Khiếu năm 2019 – 2020. Mình được một em học viên hỏi và đã hướng dẫn chi tiết cho em ấy, tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ ở đây. Hi vọng mang đến được giá trị cho các bạn 🥰.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJTrước tiên các bạn cần biết: trong C++ đã có sẵn hàm tìm ước chung lớn nhất của 2 số nguyên: __gcd(a, b) (ở đầu là 2 dấu gạch dưới), độ phức tạp $O(\log(\min(a, b)))$. Python thì có math.gcd(a, b).
Vậy cần tìm ước chung lớn nhất của nhiều số thì sao? Ví dụ 3 số $a, b, c$ thì chính là __gcd(__gcd(a, b), c). Cứ "gộp" dần như vậy cho nhiều số thì kết quả sau cùng chính là ước chung lớn nhất của cả dãy.
Mình giải thích ví dụ mẫu cho bạn nào chưa hiểu đề: $n = 10$, $k = 3$, ta có $n - k + 1 = 8$ đoạn con liên tiếp độ dài 3:
| Đoạn | Các phần tử | GCD |
|---|---|---|
| 1 → 3 | {2, 6, 4} | 2 |
| 2 → 4 | {6, 4, 3} | 1 |
| 3 → 5 | {4, 3, 18} | 1 |
| 4 → 6 | {3, 18, 12} | 3 |
| 5 → 7 | {18, 12, 24} | 6 |
| 6 → 8 | {12, 24, 8} | 4 |
| 7 → 9 | {24, 8, 7} | 1 |
| 8 → 10 | {8, 7, 5} | 1 |
Trong các GCD tìm được $\{2, 1, 1, 3, 6, 4, 1, 1\}$ thì $6$ là lớn nhất nên đáp án in ra $6$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn từng đoạn – O((N−K+1)·K·log A)
Ý tưởng đơn giản nhất: xét qua tất cả các đoạn con liên tiếp có độ dài $K$, với mỗi đoạn thì đi tìm GCD của nó bằng cách gộp dần từng phần tử, và kết quả là giá trị lớn nhất trong tất cả các GCD đó – đúng y như bảng ở trên.
Mình dùng 2 biến l, r là đầu và cuối đoạn: bắt đầu từ l = 1, r = k, mỗi lần xong một đoạn thì cùng tăng l++, r++ để "trượt" sang đoạn kế tiếp, cho tới khi r vượt quá n.
Max = 1 là an toàn, đáp án không bao giờ nhỏ hơn 1.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int l = 1, r = k;
long long Max = 1;
while(r <= n){
long long x = a[l];
for(int i = l + 1; i <= r; ++i){
x = __gcd(x, a[i]);
}
Max = max(Max, x);
l++;
r++;
}
cout << Max;
return 0;
}import sys
import math
input_data = sys.stdin.read().split()
idx = 0
n = int(input_data[idx])
idx += 1
k = int(input_data[idx])
idx += 1
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(input_data[idx])
idx += 1
l = 1
r = k
Max = 1
while r <= n:
x = a[l]
for i in range(l + 1, r + 1):
x = math.gcd(x, a[i])
Max = max(Max, x)
l += 1
r += 1
print(Max)Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ cần mảng $a$ nên là $O(N)$.
- Thời gian: xét qua $N - K + 1$ đoạn con, mỗi đoạn có $K$ phần tử và gọi hàm gcd liên tục, nên là $O((N-K+1) \cdot K \cdot \log A)$ với $A$ là giá trị lớn nhất của $a_i$.
Cách 2Chia cụm K phần tử, ghép GCD trái/phải – O(N·log A)
Bây giờ mình chia mảng $N$ phần tử thành các cụm $K$ phần tử liên tiếp. Ví dụ $N = 20$, $K = 5$ thì có 4 cụm: $[1..5]$, $[6..10]$, $[11..15]$, $[16..20]$ (nếu $N$ không chia hết cho $K$ thì cụm cuối ngắn hơn, không sao cả).
Ta tạo 2 mảng left và right, mỗi mảng có $N$ phần tử, nhưng tính riêng trong từng cụm:
left[i]= GCD từ đầu cụm chứa $i$ tới $i$ (đi từ trái qua phải). Ở cụm $[1..5]$:left[1] = a[1],left[2] = gcd(left[1], a[2]), …,left[5] = gcd(left[4], a[5]). Sang cụm mới thì bắt đầu lại:left[6] = a[6]chứ không phảigcd(left[5], a[6])đâu nha.right[i]= GCD từ $i$ tới cuối cụm chứa $i$ (đi từ phải qua trái). Ở cụm $[1..5]$:right[5] = a[5],right[4] = gcd(a[4], right[5]), …,right[1] = gcd(a[1], right[2]). Cụm $[6..10]$ lại bắt đầu từright[10] = a[10].
Có 2 mảng này rồi thì nhìn lại các đoạn cần tính GCD với $N = 20$, $K = 5$. Một đoạn độ dài $K$ bất kỳ hoặc trùng khít một cụm, hoặc vắt qua đúng một ranh giới giữa 2 cụm liền nhau:
| Đoạn cần tính | Bản chất là | Dùng mảng |
|---|---|---|
| a[1..5] | trùng khít cụm 1 | left[5] |
| a[2..6] | gcd( a[2..5] , a[6..6] ) | gcd(right[2], left[6]) |
| a[3..7] | gcd( a[3..5] , a[6..7] ) | gcd(right[3], left[7]) |
| a[4..8] | gcd( a[4..5] , a[6..8] ) | gcd(right[4], left[8]) |
| a[5..9] | gcd( a[5..5] , a[6..9] ) | gcd(right[5], left[9]) |
| a[6..10] | trùng khít cụm 2 | left[10] |
| a[7..11] | gcd( a[7..10] , a[11..11] ) | gcd(right[7], left[11]) |
| … | … | … |
- Nếu $r \bmod K = 0$: đoạn trùng khít một cụm ⇒ GCD là
left[r]. - Ngược lại: đoạn vắt qua ranh giới ⇒ GCD là
gcd(right[l], left[r]). Vìright[l]là GCD từ $l$ tới cuối cụm của $l$, cònleft[r]là GCD từ đầu cụm của $r$ tới $r$ – hai phần này ghép lại vừa khít đoạn $[l, r]$.
Vì sao đoạn độ dài $K$ không bao giờ vắt qua 2 ranh giới? Vì giữa 2 ranh giới là trọn một cụm $K$ phần tử, đoạn phải dài ít nhất $K + 2$ mới vắt qua được cả hai. Nên mỗi đoạn chỉ cần 1 lần gọi gcd là xong 😎.
- Vị trí $i$ là đầu cụm khi
i % k == 1(các vị trí $1, K+1, 2K+1, \dots$). Riêng khi $K = 1$ thì không có trường hợp này, nhưng đề cho $K \ge 2$ nên yên tâm. - Vị trí $i$ là cuối cụm khi
i % k == 0hoặci == n– vì cụm cuối có thể bị thiếu (khi $N$ không chia hết cho $K$), lúc đó phần tử $a_n$ là cuối cụm.
Minh hoạ mảng left / right và các đoạn
Em nhập dãy $a$ và $k$ rồi bấm Tiếp để xem từng bước: dựng left (trái → phải trong mỗi cụm), dựng right (phải → trái), rồi trượt từng đoạn và lấy đúng 2 ô cần dùng:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> a(n + 1), left(n + 1), right(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(i % k == 1){
left[i] = a[i];
}
else{
left[i] = __gcd(left[i - 1], a[i]);
}
}
for(int i = n; i >= 1; --i){
if(i % k == 0 || i == n){
right[i] = a[i];
}
else{
right[i] = __gcd(right[i + 1], a[i]);
}
}
int l = 1, r = k;
long long Max = 1;
while(r <= n){
if(r % k == 0){
Max = max(Max, left[r]);
}
else{
Max = max(Max, __gcd(right[l], left[r]));
}
l++;
r++;
}
cout << Max;
return 0;
}import sys
import math
input_data = sys.stdin.read().split()
idx = 0
n = int(input_data[idx])
idx += 1
k = int(input_data[idx])
idx += 1
a = [0] * (n + 1)
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(input_data[idx])
idx += 1
if i % k == 1:
left[i] = a[i]
else:
left[i] = math.gcd(left[i - 1], a[i])
for i in range(n, 0, -1):
if i % k == 0 or i == n:
right[i] = a[i]
else:
right[i] = math.gcd(right[i + 1], a[i])
l = 1
r = k
Max = 1
while r <= n:
if r % k == 0:
Max = max(Max, left[r])
else:
Max = max(Max, math.gcd(right[l], left[r]))
l += 1
r += 1
print(Max)Đánh giá độ phức tạp của cách làm này:
- Không gian: 3 mảng
a,left,rightnên là $O(N)$. - Thời gian: dựng 2 mảng
left,rightchỉ duyệt qua $N$ phần tử, mỗi phần tử gọi gcd 1 lần ⇒ $O(N \cdot \log A)$. Bước xét $N - K + 1$ đoạn, mỗi đoạn gọi gcd đúng 1 lần ⇒ $O((N - K) \cdot \log A)$. Lấy thành phần lớn nhất ⇒ tổng là $O(N \cdot \log A)$.
Với $N = 10^5$, $\log(10^{18}) \approx 60$ thì $N \cdot \log A = 6 \cdot 10^6$, tức là chỉ khoảng 6 triệu phép tính, nhỏ hơn rất nhiều so với ngưỡng 100 triệu/giây nên yên tâm không bị TLE.
long long (tối đa khoảng $9.2 \cdot 10^{18}$), dùng int là tràn ngay. Biến Max cũng phải là long long.- 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