思路:

区间乘积的因数个数显然符合单调性。区间越长，其因数个数越多。所以双指针一下即可。

复杂度:$O(n*p(a_i))$

其中函数$p(a_i)$ 代表$a_i$唯一分解定理表示法中本质不同的质数的个数.可以发现他显然是小于 $log a_i$的。所以复杂度够

题目内容

小红是一名年轻的数学家，他一直对数学充满热情。有一天，他在研究数论时发现了一个有趣的问题：给定一个长度为 $n$ 的数组 $a$，问有多少个子数组的乘积的因数个数 $≥k$。

小红对这个问题非常感兴趣，因为它可以帮助他更好地了解因数的性质，但是现在研究出现了一些问题，他想请你帮忙解决一下这个问题，你能帮小红解决这个问题吗？

输入描述

第一行为两个整数 $n$ 和 $k$ ，（ $1\le n \le 2\times 10^5$ ，$1\le k \le 10^9$ ）。

第二行为 $n$ 个整数，第 $i$ 个数为 $a_i$ ，（ $1\le a_i \le 2\times 10^5$ ）。

输出描述

输出为一个整数，表示有多少个子数组的乘积的因数个数 $≥k$。

样例1

输入

5 3
1 3 7 5 4

输出

10

样例2

输入

8 5
1 3 4 6 7 11 10 3

输出

26

建议:

python选手使用pypy3提交获得更快的速度

ps:目前各大笔试平台只有牛客提供pypy3编译器，能够跟C++去比比赛。其他平台，遇到py被卡，基本只能自认倒霉。当然这种情况也只会出现在压轴题。