Ước Lớn Nhất (BESTUOC)
Đề bài
Sắp đến đợt kiểm tra học kì, Nam rất lo lắng về điểm môn tin học. Vì Nam là 1 học sinh giỏi toàn diện nên cậu muốn điểm môn tin phải cao. Sau khi học tất cả kiến thức cơ bản, cậu thấy môn tin học cực kì dễ dàng. Đến hôm kiểm tra, thầy cho 1 bài khá khó nên Nam không làm được, vì thế nên Nam nhờ các Luyencode Coder làm hộ bài.
Đề bài: cho 1 dãy $a_i$ có $n$ phần tử. Bạn hãy thay thế 1 phần tử trong đoạn $[1, 10^9]$ của dãy $a_i$ để tạo ước chung lớn nhất của dãy $a_i$. Hãy in ra ước chung lớn nhất của dãy $a_i$.
(Hiểu là: chọn đúng 1 phần tử, thay nó bằng một số nguyên bất kỳ trong đoạn $[1, 10^9]$, sao cho ước chung lớn nhất của cả dãy sau khi thay là lớn nhất có thể. In ra giá trị lớn nhất đó.)
Dữ liệu vào:
- Dòng 1 là số nguyên $n$ $(1 \le n \le 10^6)$.
- Dòng 2 là $n$ số nguyên $a_i$ $(1 \le a_i \le 10^6)$.
Dữ liệu ra: là đáp án của bài toán mà Nam nhờ code hộ.
3
4 6 33Gợi ý của đề: thay đổi $a_1$ thành bất kì số nào chia hết cho 3. Khi đó dãy là $(3k, 6, 3)$ có ước chung lớn nhất bằng $3$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm thêm đó là toàn bộ tin nhắn của mình với em ấy, để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn. Chúc các bạn học tốt và gặt hái nhiều thành công 😇.
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:
Gợi ýThay thế 1 phần tử = bỏ nó ra
Gợi ý à, hmmm… em sẽ thấy rằng việc nói thay thế 1 giá trị bất kỳ bằng 1 giá trị khác, bản chất của nó có thể nói thẳng ra là loại bỏ giá trị đó ra và tính ước chung lớn nhất của các thằng còn lại thôi 🙂.
Tại vì sao? Giả sử có 5 thằng, giờ cần thay thế 1 thằng, thì ước chung lớn nhất của 4 thằng còn lại giả sử là 4 đi, nhưng vì tính ước chung lớn nhất với cái thằng mà mình đang tính thay thế nên ước chung lớn nhất chỉ còn 2. Vậy nếu mình bỏ thằng đó ra thì ước chung lớn nhất của 4 thằng sẽ là 4 rồi, thì cái thằng mình bỏ ra mình sẽ thay thế nó chính bằng 4 luôn, hoặc 1 số bất kỳ chia hết cho 4, thì coi như ước chung lớn nhất vẫn sẽ được bảo toàn.
Chắc chắn không thể có cách nào thay thế mà ước chung lớn nhất vượt qua 4 được, tại vì đã là ước thì nó chỉ có thể từ đó giảm xuống chứ không có chuyện tăng lên.
Đó, thì em hãy nghĩ đến điều đó 😀 gợi ý của anh là như thế, nói thêm nữa sẽ mất vui nè ^^
Kiến thứcTìm UCLN của cả dãy N phần tử
Cũng nói thêm cho em biết làm thế nào để tìm được ước chung lớn nhất của dãy $N$ phần tử từ $a_1$ đến $a_n$?
Đầu tiên nó tìm ước chung lớn nhất của $a_1$ và $a_2$. Sau đó lấy ước chung lớn nhất đó và tìm ước chung lớn nhất của chính nó với $a_3$. Và cứ thế làm tương tự với $a_4, a_5, \ldots$ cho đến $a_n$. Sau cùng kết quả thu được nó là ước chung lớn nhất của dãy $N$ phần tử.
Mẹo nhỏ: $\text{UCLN}(0, x) = x$, nên có thể cho biến kết quả bắt đầu từ $0$ rồi cứ lần lượt "gộp" từng phần tử vào. Hàm __gcd của C++ và math.gcd của Python đều chạy đúng như vậy.
Ok. Với từng vị trí $i$, hãy tìm ước chung lớn nhất của toàn bộ các phần tử còn lại ngoài vị trí $i$. Và so sánh kết quả Max với lần lượt từng vị trí $i$. Ví dụ test 4 6 3:
| Vị trí bỏ | Dãy | UCLN phần còn lại | |
|---|---|---|---|
| Bỏ đi 4 | 463 | UCLN(6, 3) = 3 | ✔ Max |
| Bỏ đi 6 | 463 | UCLN(4, 3) = 1 | |
| Bỏ đi 3 | 463 | UCLN(4, 6) = 2 |
⇒ Max chọn 3.
Cách 1Vét cạn: bỏ từng vị trí rồi tính lại – O(N² log A)
Làm đúng y như gợi ý trên: với mỗi $i$, duyệt lại cả dãy (trừ $a_i$) để tính UCLN. Code này mình viết thêm để các bạn dễ hình dung và để dùng làm code đối chứng:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
if(n == 1){
cout << 1000000000;
return 0;
}
int Max = 0;
for(int i = 0; i < n; ++i){
int g = 0;
for(int j = 0; j < n; ++j){
if(j != i){
g = __gcd(g, a[j]);
}
}
Max = max(Max, g);
}
cout << Max;
return 0;
}import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
if n == 1:
print(10**9)
else:
Max = 0
for i in range(n):
g = 0
for j in range(n):
if j != i:
g = gcd(g, a[j])
Max = max(Max, g)
print(Max)Riêng trường hợp $n = 1$: bỏ phần tử duy nhất đi thì không còn ai ràng buộc, ta thay nó bằng số lớn nhất được phép là $10^9$, UCLN của dãy 1 phần tử chính là nó, nên đáp án là $10^9$.
Nhưng chẳng lẽ cứ mỗi lần không tính 1 vị trí $i$ mà ta lại phải duyệt lại toàn bộ $n - 1$ phần tử để tìm ước chung lớn nhất (gọi tắt là UCLN)? Như thế thì rất lâu. Bởi vì UCLN của $n - 1$ phần tử là phải xét qua $n - 2$ cặp, với mỗi cặp tìm ra UCLN của 2 đứa. Em có biết là hàm __gcd có sẵn tìm UCLN của 2 số nó được xây dựng tối ưu rồi thì độ phức tạp sẽ là $O(\log(\min(a, b)))$ không? Mà mỗi lần loại đi 1 vị trí $i$ là phải xét $n - 2$ cặp, mà ta có đến $n$ vị trí $i$ cần xét, vậy số cặp phải xét là $n \cdot (n - 2)$. Vậy có thể thấy độ phức tạp sẽ là $n \cdot (n - 2) \cdot \log(\min(a, b))$, nội $n \cdot (n - 2)$ đã coi như $n^2$.
Bài đó cho $n$ tối đa $10^6$ thì như thế $n^2$ là phải xét qua cả $10^{12}$ cặp, là đủ TLE rồi (vì ngưỡng tối đa 1 giây chỉ là $10^8$ thôi), còn chưa tính đến chi phí tìm UCLN giữa 2 thằng. Nên chắc chắn làm như vậy sẽ bị TLE.
Cách 2Hai mảng phụ left, right – O(N log A) – AC
Đúng, cần phải có mảng phụ.
Có phải nếu mảng $n$ phần tử, với từng vị trí $i$ ta sẽ giả sử loại bỏ phần tử $a_i$ đó không tính nó, chỉ tính UCLN của các phần tử còn lại, nghĩa là UCLN của $a_0, a_1,$ $\ldots,$ $a_{i-1},$ $a_{i+1},$ $\ldots,$ $a_{n-1}$. Như Cách 1 đã phân tích, tính lại từ đầu cho mỗi $i$ thì quá lâu. Vậy nên 1 cách tốt hơn là tạo:
- Mảng
leftvới ý nghĩaleft[i]là UCLN của toàn bộ các phần tử từ đầu mảng tính đến ngay tại vị trí $i$, tức làleft[i]= UCLN$(a_0, a_1, a_2, \ldots, a_i)$. - Tương tự có mảng
rightvới ý nghĩaright[i]là UCLN của toàn bộ các phần tử từ vị trí $i$ trở về cuối mảng, tức làright[i]= UCLN$(a_i, a_{i+1}, a_{i+2}, \ldots, a_{n-1})$.
Vậy có phải khi xét đến 1 vị trí $i$ cần loại bỏ thì thay vì phải xét tìm UCLN của $n - 1$ thằng còn lại, lúc này ta chỉ cần tìm UCLN giữa thằng left[i - 1] và thằng right[i + 1] là coi như nó chính là kết quả UCLN của toàn bộ mảng sau khi đã loại thằng a[i] ra. Em ngẫm xem đúng không nè ^^
Hai đầu mút thì đặc biệt hơn chút: bỏ $a_0$ thì phần còn lại chính là right[1], bỏ $a_{n-1}$ thì phần còn lại chính là left[n - 2]. Em nhập dãy rồi bấm Tiếp để xem cả quá trình dựng 2 mảng và ghép kết quả:
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), left(n), right(n);
cin >> a[0];
left[0] = a[0];
for(int i = 1; i < n; ++i){
cin >> a[i];
left[i] = __gcd(left[i - 1], a[i]);
}
right[n - 1] = a[n - 1];
for(int i = n - 2; i >= 0; --i){
right[i] = __gcd(right[i + 1], a[i]);
}
int Max = max(right[1], left[n - 2]);
int sz = n - 1;
for(int i = 1; i < sz; ++i){
Max = max(Max, __gcd(left[i - 1], right[i + 1]));
}
cout << Max;
return 0;
}import sys
import math
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
left = [0] * n
right = [0] * n
left[0] = a[0]
for i in range(1, n):
left[i] = math.gcd(left[i - 1], a[i])
right[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
right[i] = math.gcd(right[i + 1], a[i])
Max = max(right[1], left[n - 2])
sz = n - 1
for i in range(1, sz):
Max = max(Max, math.gcd(left[i - 1], right[i + 1]))
print(Max)- Vừa đọc
a[i]vừa tính luônleft[i] = __gcd(left[i - 1], a[i]). - Duyệt ngược từ cuối để tính
right[i] = __gcd(right[i + 1], a[i]). Maxkhởi tạo bằng kết quả của 2 đầu mút:max(right[1], left[n - 2]).- Các vị trí ở giữa $1 \le i \le n - 2$:
__gcd(left[i - 1], right[i + 1]).
right[1] và left[-1], ra ngoài mảng (bản Python sẽ báo lỗi IndexError). Code này đã AC trên hệ thống nên có lẽ bộ test không có $n = 1$. Để chắc ăn, em có thể thêm vào ngay sau khi đọc $n$: if(n == 1){ cout << 1000000000; return 0; } như trong Cách 1 và Cách 3 nhé.Lúc anh đọc vào đề là sau tầm vài phút anh nghĩ ra ý tưởng này á ^^ Đại khái là cứ hãy luôn nghĩ trong đầu: hãy làm sao để tiết kiệm chi phí phải xét duyệt. Cứ luôn nghĩ về điều đó sẽ giúp ta nhìn ra được những hướng giải tốt hơn.
Thậm chí anh còn đang suy nghĩ: bài đó cả thảy anh dùng 3 mảng. Anh cho rằng có thể bỏ bớt 1 mảng đi. Em thử nghĩ xem ^^
Cách 3Bỏ bớt mảng left – lời giải câu đố của anh
Đây là phần mình viết thêm để trả lời câu đố trên, các bạn tự nghĩ trước rồi hãy đọc nha 😉. Để ý là khi duyệt $i$ từ trái sang phải, left[i - 1] chỉ được dùng đúng 1 lần rồi bỏ. Vậy thay vì lưu cả mảng left, ta dùng 1 biến g = UCLN của các phần tử đứng trước $i$, vừa duyệt vừa gộp dần:
- Tính mảng
rightnhư cũ, nhưng cho thêm 1 ôright[n] = 0(vì UCLN$(0, x) = x$, ô này đóng vai "rỗng"). - Với mỗi $i$ từ $0$ đến $n - 1$: kết quả khi bỏ $a_i$ là
__gcd(g, right[i + 1]), rồi gộp $a_i$ vào:g = __gcd(g, a[i]). - Nhờ
g = 0lúc đầu vàright[n] = 0, hai đầu mút được xử lý luôn trong cùng 1 vòng lặp, không cần tách riêng.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), right(n + 1, 0);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
if(n == 1){
cout << 1000000000;
return 0;
}
for(int i = n - 1; i >= 0; --i){
right[i] = __gcd(right[i + 1], a[i]);
}
int Max = 0, g = 0;
for(int i = 0; i < n; ++i){
Max = max(Max, __gcd(g, right[i + 1]));
g = __gcd(g, a[i]);
}
cout << Max;
return 0;
}import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
if n == 1:
print(10**9)
else:
right = [0] * (n + 1)
for i in range(n - 1, -1, -1):
right[i] = gcd(right[i + 1], a[i])
Max = 0
g = 0
for i in range(n):
Max = max(Max, gcd(g, right[i + 1]))
g = gcd(g, a[i])
print(Max)Vẫn là $O(N \log A)$ thời gian, nhưng chỉ còn 2 mảng $a$ và right. Thật ra cũng có thể bỏ luôn mảng $a$ bằng cách đọc dữ liệu 2 lần… nhưng đọc input chỉ được 1 lần thôi, nên 2 mảng là gọn nhất rồi 😄.
Nhận xét
Đăng nhận xét