Duyên hải Bắc Bộ 2025 - Ước chung
Xem dạng PDF
Gửi bài giải
Điểm:
30,00 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Khi giảng dạy về nội dung ước số chung lớn nhất, Alice đã cho học sinh bài toán sau:
Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Hãy chọn ra nhiều số nhất mà ước chung lớn nhất của chúng lớn hơn 1.
Ví dụ, với dãy số gồm bốn số 4, 5, 8, 20, có thể chọn được nhiều nhất ba số, chọn các số 4, 8, 20 có ước chung lớn nhất là 4.
Yêu cầu: Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Hãy tính số lượng số nhiều nhất chọn được thỏa mãn điều kiện bài toán.
Input
- Dòng đầu chứa số nguyên dương ~n~ (~n \le 1000~).
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^{18}~).
Output
- Ghi ra một số nguyên là số lượng số chọn được.
Sample Input 1
4
5 8 4 20
Sample Output 1
3
Sample Input 2
4
2 4 6 8
Sample Output 2
4
Subtasks
- Subtask 1 (~20 \%~): ~n = 2~ và ~a_i \le 10^6~.
- Subtask 2 (~30 \%~): ~n \le 18~.
- Subtask 3 (~30 \%~): ~a_i \le 10^6~.
- Subtask 4 (~20 \%~): Không có ràng buộc nào thêm.
Bình luận
lam nhu nao v a
brute bth
đúng god cạo đầu được đi thi dhbb, orz