k倍区间
给定一个长度为 \(N\) 的数列，\(A1,A2,…AN\)，如果其中一段连续的子序列 \(Ai,Ai+1,…Aj\) 之和是 \(K\) 的倍数，我们就称这个区间 \([i,j]\)是 \(K\) 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 \(Ai\)。
输出格式
输出一个整数，代表 K 倍区间的数目。
数据范围
\(1≤N,K≤100000,\)
\(1≤Ai≤100000\)
输入样例：
5 2
1
2
3
4
5
输出样例：
6
思路
Code
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define endl '\n'
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL cnt[N]; //防止爆int
int n,k;
LL ans,a1,a2;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> k;
cnt[0] = 1;
//余数为0时存在长度为1的k倍区间
//基数为1则如果数组中存在有长度为1的k倍区间，范围变为（0~r）
for(int i = 1; i <= n; i ++ ){
a1 = a2; //前缀和只用当前和上一个：滚动数组优化空间
cin >> a2; //输入当前
a2 += a1; //自身求前缀和
a2 %= k; //求余数
ans += cnt[a2]; //先算ans后++维护l = (0~r-1)
cnt[a2] ++;
//这两段代码的意思是r固定时，从l = (0~r-1) 找到同余的个数
//则所记录的k倍区间的长度大于1
}
cout << ans;
return 0;
}