题目内容

在数据科学领域，分析师经常需要挖掘序列中隐藏的数值特性。对于一个长度为 $n$ 的正整数序列 $x_1, x_2, \dots, x_n$，考虑它的任意一个连续子段 $x_l, x_{l+1}, \dots, x_r$ （$1 \le l \le r \le n$）。

定义该子段的乘积 $M = \prod_{i=l}^{r} x_i$，并用 $d(M)$ 表示 $M$ 的正因子个数（即能整除 $M$ 的正整数的数目）。你的任务是统计满足 $d(M) \ge k$ 的连续子段 $(l, r)$ 的总个数。

关于计算正因子个数，可以利用经典的约数个数定理：若 $M$ 的质因数分解为 $M = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$，则 $d(M) = (e_1+1)(e_2+1)\cdots(e_t+1)$。

序列的长度 $n$ 不超过 $2 \times 10^5$，阈值 $k$ 不超过 $10^9$。序列中每个数 $x_i$ 均为不超过 $2 \times 10^5$ 的正整数。

输入描述

第一行包含两个整数 $n$ 和 $k$，用空格分隔。 第二行包含 $n$ 个整数，依次表示 $x_1, x_2, \dots, x_n$，相邻整数之间用空格分隔。

输出描述

输出一个整数，表示满足 $d(M) \ge k$ 的连续子段个数。

样例1

输入

4 3
2 6 1 3

输出

6

说明

序列为 $[2, 6, 1, 3]$，阈值 $k=3$。

枚举所有连续子段并计算乘积的正因子个数 $d(M)$：

• $[2]$：$M=2=2^1$，$d(M)=1+1=2 < 3$；
• $[2,6]$：$M=12=2^2 \times 3^1$，$d(M)=(2+1)(1+1)=6 \ge 3$；
• $[2,6,1]$：$1$ 不影响乘积，$d(M)=6 \ge 3$；
• $[2,6,1,3]$：$M=36=2^2 \times 3^2$，$d(M)=(2+1)(2+1)=9 \ge 3$；
• $[6]$：$M=6=2^1 \times 3^1$，$d(M)=4 \ge 3$；
• $[6,1]$：$d(M)=4 \ge 3$；
• $[6,1,3]$：$M=18=2^1 \times 3^2$，$d(M)=2 \times 3 =6 \ge 3$；
• $[1]$：$M=1$，$d(M)=1 < 3$；
• $[1,3]$：$M=3$，$d(M)=2 < 3$；
• $[3]$：$M=3$，$d(M)=2 < 3$。

满足条件的子段共有 6 个。

样例2

输入

1 5
16

输出

1

说明

序列只有一个元素 $16$，阈值 $k=5$。

$M=16=2^4$，其正因子个数 $d(M)=4+1=5$，满足 $d(M) \ge 5$。唯一的子段 $[16]$ 计入答案，故输出 1。

样例3

输入

3 1
5 7 11

输出

6

说明

序列为 $[5, 7, 11]$，阈值 $k=1$。

任何正整数的正因子个数 $d(M) \ge 1$ 恒成立，因此所有连续子段均满足条件。长度为 $3$ 的序列共有 $3 \times 4 / 2 = 6$ 个连续子段，答案为 6。