재생목록의 최대공약수 구간

문제

어느 음악 스트리밍 서비스의 재생목록에는 곡이 N개 순서대로 놓여 있다. i번째 곡의 길이는 a_i 초이며 양의 정수이다. 재생목록에서 연속한 곡들을 묶은 것을 구간이라 부른다. 구간 [l, r] (1 ≤ l ≤ r ≤ N)은 l번째 곡부터 r번째 곡까지를 뜻하며, 곡 하나만으로 이루어진 구간도 구간이다. 구간의 박자 값은 그 구간에 포함된 곡들의 길이의 최대공약수로 정의한다. 곡이 하나뿐인 구간의 박자 값은 그 곡의 길이이다. 이 서비스는 박자 값이 정확히 G 인 구간만 추천 묶음으로 사용한다. 박자 값이 G 의 배수이더라도 G 보다 크면 추천 묶음이 아니다. 곡의 길이가 같더라도 시작 위치나 끝 위치가 다르면 서로 다른 구간으로 센다. 추천 묶음으로 쓸 수 있는 구간의 개수를 구하는 프로그램을 작성하시오. 그런 구간이 하나도 없다면 0을 출력한다. 답은 32비트 정수 범위를 넘을 수 있다.

입력

첫 줄에 곡의 수 N 과 정수 G 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ G ≤ 1,000,000,000)
둘째 줄에 곡의 길이 a_1, a_2, ..., a_N 이 공백으로 구분되어 주어진다. (1 ≤ a_i ≤ 1,000,000,000)

출력

박자 값이 정확히 G 인 구간의 개수를 한 줄에 출력한다.

6 2
4 6 8 3 2 10

5

3 7
7 7 7

6

2 3
2 4

0

출처: Devin.KR 자체 제작