题目内容

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

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

思路:

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

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

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