首页 > 试题广场 >

多多的求和计算

[编程题]多多的求和计算
  • 热度指数：7074 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。
多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述:
第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100  ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）


输出描述:
共1行，每行1个整数，表示满足整体是和谐的区间的数量。
示例1

输入

5 2
1 2 3 4 5

输出

6

说明

长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。

备注:
对于50%的数据，有N<=1,000
对于100%的数据，有N<=100,000
算法知识视频讲解
添加回答
JavaScript
牛客645135900号头像 牛客645135900号 
var firstline=readline().split(" ")
var listlen=parseInt(firstline[0])
var harmonum=parseInt(firstline[1])
var list=readline().split(" ")
var lista=list.map(item=>parseInt(item))
//存放0-i位置的数组和的余数
var leftnum=[]
var sumtmp=0
var ans=0
//存放某个余数的出现个数
var map=new Map([[0,0]])
for(var i=0;i<listlen;i++){
    sumtmp+=lista[i]
    if(sumtmp%harmonum==0){ans+=1}
    if(!map.has(sumtmp%harmonum)){
        map.set(sumtmp%harmonum,1)
    }else{
        ans+=map.get(sumtmp%harmonum)
        map.set(sumtmp%harmonum,map.get(sumtmp%harmonum)+1)
    }
}
console.log(ans)
js版本

发表于 2022-04-11 16:11:38 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 拼多多 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
1条回答 9536浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号