Tìm ước chung lớn nhất (HSG9 VT 2023)
Xem PDF
Nộp bài
Điểm:
1200 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
CDIV.inp
Output:
CDIV.out
Tác giả:
Dạng bài
Cho một mảng A gồm N số nguyên dương: a_1, a_2, \dots, a_N
Yêu cầu: Hãy tìm hai số nguyên trong mảng A sao cho ước chung lớn nhất của 2 số đó là lớn nhất
Input và Output
Input: (CDIV.inp)
- Dòng đầu tiên chứa số nguyên N (2\le N\le 2\cdot 10^5)
- Dòng thứ hai chứa N số nguyên a_i, mỗi số cách nhau một ký tự trắng (1\le a_i\le 10^6)
Output: (CDIV.out)
- Một số nguyên duy nhất là ước chung lớn nhất tìm được
Bonus
Bạn có thể giải bài toán này với N\le 10^6, a_i\le 10^7 ?
Subtasks
- Subtask 1 (10\%): N\le 10.
- Subtask 2 (15\%): N\le 2^{15}.
- Subtask 3 (25\%): N\le 2\cdot 10^5.
- Subtask 4 (50\%): Không có giới hạn gì thêm.
Sample
Input (CDIV.inp)
6
12 5 6 4 7 10
Output (CDIV.out)
6
Bình luận