Dãy con có ước chung lớn hơn 1
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy gồm $N$ số nguyên dương $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$). Hãy chọn ra một dãy con có nhiều phần tử nhất sao cho ước chung lớn nhất (GCD) của tất cả các phần tử được chọn lớn hơn $1$.
Lưu ý: Nếu chỉ chọn 1 phần tử $a_i > 1$ thì GCD của dãy con đó chính là $a_i > 1$ (hợp lệ). Nếu tất cả phần tử đều bằng $1$, đáp án là 0.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$).
Dữ liệu ra
- Độ dài lớn nhất của dãy con thỏa mãn.
Ví dụ
| Input | Output |
|---|---|
| 5 2 3 4 6 9 |
3 |
Giới hạn
- $1 \le N \le 10^5, 1 \le a_i \le 10^6$
Community Discussion