CSES - Common Divisors | Ước chung
Xem PDF
Điểm:
1500
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng gồm \(n\) số nguyên dương. Việc của bạn là tìm hai số nguyên sao cho ước chung lớn nhất của chúng càng lớn càng tốt.
Input
- Dòng đầu tiên là một số nguyên \(n:\) kích thước của mảng.
- Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,...,x_n\): các phần tử của mảng.
Output
- In ra ước chung lớn nhất tối đa.
Constraints
- \(2 \le n \le 2 \cdot 10^5\)
- \(1 \le x_i \le 10^6\)
Example
Sample input
5
3 14 15 7 9
Sample output
7
Bình luận
Nhớ thêm dấu # tui ko biết thêm vào hihi
include<bits/stdc++.h>
using namespace std;
long long a[10000006];
unordered_map<int, int> m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
m[a[i]]++;
}
int maxx = *max_element(a, a + n);
for (int i = maxx; i >= 1; i--) {
int count = 0;
for (int j = i; j <= maxx; j += i) {
count += m[j];
if (count >= 2) {
cout << i << "\n";
return 0;
}
}
}
return 0;
}
sigma boy , sigma boy , sigma boy , sigma boy
skibidi toilet , skibidi toilet , skibidi toilet ,
4 bình luận nữa