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) 

#字节跳动笔试##字节跳动##晒一晒我的offer##牛客在线求职答疑中心#
全部评论

相关推荐

醉蟀:你不干有的是人干
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务