思路:

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

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

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

还有个知识点你可能需要知道：约数个数定理

from collections import defaultdict
n , k = list(map(int , input().split()))
a = list(map(int , input().split()))
maxa = 200005
f = [defaultdict(int) for i in range(maxa)]
p = [True] * maxa
# 类似埃氏筛的去转移，求解每个数其唯一分解定理表示法(质数,指数大小)。用dict存储
for i in range (2 , maxa):
	if not p[i]:
		continue
	f[i][i] = 1
	for j in range (i + i, maxa , i):
		if i in f[j // i]:
			f[j][i] = f[j // i][i] + 1
		else:
			f[j][i] = 1
		p[j] = False
# 双指针 - now_f 代表当前区间累积的唯一分解表示法 , now_val 代表当前区间累积的约数个数
now_f = defaultdict(int)
now_val = 1
ans = 0
i = 0
j = 0
while j < n:
    # 根据<约数个数定理>,进行转移更新
	for x in f[a[j]]:
		now_val //= now_f[x] + 1
		now_f[x] += f[a[j]][x]
		now_val *= now_f[x] + 1
	while now_val >= k and i <= j:
        # 根据<约数个数定理>,进行转移更新
		for x in f[a[i]]:
			now_val //= now_f[x] + 1
			now_f[x] -= f[a[i]][x]
			now_val *= now_f[x] + 1
		i += 1
	ans += i
	j += 1
	
print(ans)

题目内容

小红是一名年轻的数学家，他一直对数学充满热情。有一天，他在研究数论时发现了一个有趣的问题：给定一个长度为 $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被卡，基本只能自认倒霉。当然这种情况也只会出现在压轴题。