蓝桥杯 k倍区间
题目描述
给定一个长度为 NN 的数列，A1,A2,⋯ANA1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1,⋯AjAi,Ai+1,⋯Aj ( i≤ji≤j ) 之和是 KK 的倍数，我们就称这个区间 [i,j][i,j] 是 K 倍区间。
你能求出数列中总共有多少个 KK 倍区间吗？
输入描述
第一行包含两个整数 NN 和 KK( 1≤N,K≤1051≤N,K≤105 )。
以下 N 行每行包含一个整数 AiAi ( 1≤Ai≤1051≤Ai≤105 )
输出描述
输出一个整数，代表 K 倍区间的数目。
输入输出样例
示例
输入
5 2 1 2 3 4 5输出
6运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
前缀和数组对k取余，余数相同时
#include <iostream>
using namespace std;
long long int nums[100100];
int cnt[100100];
int main()
{
int n, k;
long long int res = 0;
cin>>n>>k;
for(int i=1; i<=n; i++){
int cur;
cin>>cur;
nums[i] += cur + nums[i-1];
if(nums[i] % k == 0){
++res;
}
res += cnt[ nums[i] % k ];
++cnt[ nums[i] % k];
}
cout<<res;
return 0;
}，两两之间就是k倍子区间