Solutions of Maximum GCD

Select solution language

giavinh650 Created at 15 likes

# 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