Dãy con có ước chung lớn hơn 1

Buổi 71-72 — Ôn tập Number Theory
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved