Tối giản

View as PDF

Submit solution


Points: 0.00 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản. ~(1 \le l < r \le 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]~.

Comments

Please read the guidelines before commenting.



  • -12
    NamHai  commented on Jan. 7, 2023, 7:55 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      lkva2019  commented on March 12, 2023, 3:06 a.m.

      ~6~ không chia hết cho ~4~ bạn nhé