10-8 字节笔试 乘积为k的连续子数组数量

题目描述：
小红拿到了一个大小为n的数组，他想知道，有多少连续子数组满足，该子数组所有元素的乘积是k的倍数？

输入输出：
第一行输入2个整数，分别是数组长度n和参数k
第二行输入n个元素的数组

n有10^5级别
数组元素有10^6级别
k有10^12级别

样例
input
3 6
2 3 4

output
3

一开始我怎么也只能想到一个办法，就是前缀乘然后二重for遍历，后来看到一个题目才豁然开朗，那就是LC974，这个题目说的是和为可被k整除的子数组数量，稍有不同但是原理相同。为什么这么说呢？ 因为他用到了一个叫做同余定理的东西，就是说：如果一个数组arr，他从第i个到x-1个数组和对k的余数 = 从第i个到第y个（y在x-1的后面）的数组和对k的余数的话，就意味着这个数组从第x个到第y个的累加和是能够整除k的。这里给一篇好理解的帖子：https://blog.csdn.net/weixin_43766753/article/details/10638644

然后思路就呼之欲出了，其实累乘也是一样的，如果能够用一个哈希表存储每个子数组的余数，从前往后一次遍历，去找存不存在之前出现过的同余的子数组，如果有那么答案可以加上这个数量。

代码如下：

比较简洁，更多是思维难，值得一提的是，要事先设定cnt[0] = 1，余数为0的时候哈希表计数为1。因为这样才可以计算到本身就是可以整除k的子数组和。

n,k = list(map(int,input().strip().split()))
arr = list(map(int,input().strip().split()))
premul = [1]
for x in arr:premul.append(premul[-1]*x)
cnt = dict()
cnt[0] = 1
res = 0
for i in range(1,len(premul)):
    yu = premul[i]%k
    if yu in cnt:
       res+=cnt[yu]
       cnt[yu]+=1
    else:cnt[yu] = 1
print(res)