# Nhắc nhở:
### Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo
### Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm
___________________________________________________________________________________
### Cách 1: duyệt lần lượt
Ta sẽ duyệt 2 vòng lặp lồng nhau, vòng thứ nhất với $i$ từ 1 đến $n$ (để chọn ra 1 số cần thay) và vòng thứ hai với $j$ (trong mỗi lần duyệt $i$) từ 1 đến $n$
để tìm ra đáp án (lấy max của UCLN của tất cả các giá trị từ 1 đến $n$ sau khi thay phần tử $A_i$).
Độ phức tạp: $O$($n^2 * \log(n)$)
### Cách 2: lưu UCLN 2 đầu
(Credit to [Anh Quân](https://marisaoj.com/user/khongphaiquan/submissions) cho lời giải này)
Thay vì chúng ta tìm số để thay thế thì chúng ta sẽ tìm UCLN của tất cả các số ở 2 mảng con (bên trái và bên phải số cần thay).
Như vậy, chúng ta sẽ lưu UCLN của các số từ 1 đến $n$ (tức mảng con bên trái của số cần thay(**1**))
và lưu UCLN của các số từ $n$ về 1 (tức mảng con bên phải của số cần thay(**2**)).
Sau khi lưu, chúng ta chỉ cần duyệt $i$ từ 1 đến $n$ và tìm UCLN của tất cả phần tử của 2 mảng con
từ [1...$i$-1] và [$i$+1...n] (**3**) (vì chúng ta đã lưu trước đó nên việc này chỉ mất thời gian $O$($\log(n)$ vì phải tính UCLN, nhanh hơn so với thời gian $O$($n^2 * \log(n)$) cho mỗi lần duyệt
với cách 1)
Độ phức tạp: $O$($n * \log(n)$)
## Bài giải:
> Giải thuật: lưu UCLN 2 đầu
> Độ phức tạp: $O$($n$ * $\log(n)$)
> Ngôn ngữ lập trình: **C++ 11**
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10; int a[N],forw[N],backw[N];
//forw[] là để đánh dấu UCLN của tất cả các số trong khoảng [1..i]
//tức là đánh dấu UCLN của TẤT CẢ các số ở bên trái số cần thay
//backw[] là để đánh dấu UCLN của tất cả các số trong khoảng [i..n]
//tức là đánh dấu UCLN của TẤT CẢ các số ở bên phải số cần thay
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,i,ma=0; forw[0]=1; backw[100001]=1;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
if (i==1) forw[i]=a[i];
else forw[i]=__gcd(forw[i-1],a[i]); // (1)
}
for(i=n;i>=1;i--)
{
if (i==n) backw[i]=a[i];
else backw[i]=__gcd(backw[i+1],a[i]); // (2)
}
for(i=1;i<=n;i++) ma=max(ma,__gcd(forw[i-1],backw[i+1])); // (3)
//chúng ta sẽ không xét đến việc thay thế số cần thay
//vì dù chúng ta có thay thế như thế nào
//thì UCLN LỚN NHẤT của toàn bộ dãy sau khi thay vẫn luôn cố định
cout<<ma;
}
```
### Lưu ý: có thể có nhiều hơn một cách làm nên các bạn không nhất thiết phải làm theo lời giải
giavinh650
Created at
2 likes