P8649 [蓝桥杯 2017 省 B] k 倍区间
P8649 [蓝桥杯 2017 省 B] k 倍区间原题链接：点击查看
数据范围：
[*]\(1 \le N,K \le 10^5\)
[*]\(1 \le A_i \le 10^5\)
解题思路
前缀和 + 模运算
[*]区间 \(\) 的和 = \(pre - pre\)
[*]若该区间和是k的倍数，则满足 \((pre - pre) \bmod k = 0\)，即 \(pre \bmod k = pre \bmod k\)
[*]用数组统计每个余数出现的次数，遍历过程中累加对应余数的计数，即可得到总区间数
[*]初始化余数0的计数为1，处理前缀和本身就是k倍数的情况
复杂度分析
[*]时间复杂度：\(O(N)\)，仅遍历一次数组，常数级操作
[*]空间复杂度：\(O(K)\)，开辟长度为k的计数数组
代码实现
int n,k,x; LL ans=0; cin>>n>>k; vectorcnt(k,0); cnt=1; LL pre=0; rep(i,0,n){ cin>>x; pre=(pre+x)%k; // 累加当前余数已出现的次数 ans+=cnt; cnt++; } cout
页:
[1]