Tối giản
Xem dạng PDF
Gửi bài giải
Điểm:
0,30 (OI)
Giới hạn thời gian:
0.5s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một dãy số ~(b_1, b_2, ..., b_m)~ được gọi là có thể tối giản nếu tồn tại một phần tử ~x~ thỏa mãn:
~x~ là duy nhất trong dãy.
Mọi phần tử ~b_1, b_2, ..., b_m~ đều chia hết cho ~x~.
Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~, hãy đếm số cặp chỉ số ~(l, r)~ ~(1 \le l < r \le n)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản.
Input
Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 3 * 10^5)~.
Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.
Output
- Gồm một dòng duy nhất là số dãy tìm được.
Sample Input 1
5
4 3 6 4 2
Sample Output 1
3
Notes
- Các đoạn thỏa mãn là ~[2, 3], [4, 5], [3, 5]~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
~6~ không chia hết cho ~4~ bạn nhé