# 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
Chúng ta sẽ duyệt lần lượt từng cặp số ($A_i$, $A_j$) để lấy ước chung lớn nhất.
> Các bạn có thể sử dụng [Giải thuật Euclid](https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid) để tìm UCLN với thời gian tối ưu (độ phức tạp $O$($log(n)$).
> Có thể sử dụng hàm `__gcd()` trong C++ để tìm UCLN của 2 số (cũng dùng giải thuật Euclid).
Độ phức tạp: $O$($n^2 * log(n)$)
### Cách 2: Sàng đếm
Cải tiến của sàng nguyên tố: lưu các giá trị được nhập vào 1 mảng đánh dấu, rồi duyệt $i$ từ 1 đến giá trị ước lớn nhất có thể ($10^6$)
Với mỗi lần duyệt, chúng ta sẽ lại duyệt các bội của $i$, cộng vào số lượng số là bội của $i$ vào mảng đếm (tức với
mỗi giá trị $i$, chúng ta sẽ đếm xem có bao nhiên số nhập vào là bội của $i$, hay có bao nhiêu số lấy $i$ làm ước).
Cuối cùng, chúng ta sẽ duyệt mảng đếm xem có ước nào có ít nhất 2 số chia hết thì lấy $max$, rồi in ra $max$ sau khi duyệt.
Độ phức tạp: $O$($N$ * $\log(n)$)
## Bài giải:
> Giải thuật: sàng đếm
> Độ 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=1e6+10;
int a[N]={}; //mảng đánh dấu
int f[N]={}; //mảng đếm các số là bội của các giá trị
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,i,res,x,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x; a[x]++; //đánh dấu các giá trị nhập vào
}
for(i=1;i<=N-10;i++)
{
for(j=i;j<=N-10;j+=i) f[i]+=a[j];
}
for(i=N-10;i>=1;i--)
{
if (f[i]>1)
{
cout<<i; return 0; //bước này in ra kết quả luôn vì duyệt ngược
// tức số đầu tiên tìm được sẽ là lớn nhất
}
}
}
```
### 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
7 likes