Mô tả
Anh Ba làm tổ trưởng tổ vận hành lưới điện miền quê Thái Bình. Mỗi trạm biến áp trong vùng anh phụ trách đều có một chu kỳ bảo trì riêng — cứ bao nhiêu tháng thì phải kiểm tra một lần. Ví dụ, trạm đầu làng cần kiểm tra mỗi 4 tháng, trạm xã thì 6 tháng, trạmfield sau đồng thì 8 tháng. Anh Ba muốn xếp một lịch bảo trì tổng thể sao cho cứ hết một chu kỳ chung là đi kiểm tra toàn bộ, không sót trạm nào. Hãy giúp anh Ba tìm chu kỳ chung ngắn nhất, chính là ước chung lớn nhất của tất cả các chu kỳ.
Đầu vào
Dữ liệu vào gồm một mảng số nguyên dương a, trong đó a[i] là chu kỳ bảo trì (tính theo tháng) của trạm biến áp thứ i.
Đầu ra
Trả về một số nguyên dương duy nhất là ước chung lớn nhất của toàn bộ các phần tử trong mảng a.
Ràng buộc
- 1 ≤ n ≤ 10^5 (số lượng trạm biến áp).
- 1 ≤ a[i] ≤ 10^9 (chu kỳ bảo trì mỗi trạm, tính theo tháng).
Ví dụ
Giả sử danh sách chu kỳ bảo trì các trạm là [4, 6, 8].
- ước chung lớn nhất của 4 và 6 là 2.
- ước chung lớn nhất của 2 và 8 cũng là 2.
- Vậy kết quả trả về là
2, anh Ba sẽ lên lịch kiểm tra tổng thể cứ 2 tháng một lần.