You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最大公约数

题目描述

给定一个长度为 $n$ 的正整数序列 $a_n$ 和一个正整数 $k$, 请你计算 $a_n$ 的子数组中所有元素的最大公约数等于 $k$ 的子数组数目.

子数组是数组中一个连续的非空序列. 本题中，两个子数组不同，当且仅当它们在原数组中的位置不完全相同.

数组的最大公约数是能整除数组中所有元素的最大整数.

输入

共 $2$ 行，第一行包含两个整数 $n, k$，第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$.

输出

一个整数，表示所有元素的最大公约数为 $k$ 的子数组个数.

数据范围

$1 \le n \le 5 \times 10^5$

$1 \le k, a_i \le 10^9$

输入样例

6 3
9 3 1 2 6 3

输出样例

4

样例解释

$a_n$ 的子数组中，以 $3$ 作为最大公因数的子数组如下：

• $\textbf{9}, \textbf{3}, 1, 2, 6, 3$
• $9, \textbf{3}, 1, 2, 6, 3$
• $9, 3, 1, 2, \textbf{6}, \textbf{3}$
• $9, 3, 1, 2, 6, \textbf{3}$