题目描述
给定一个长度为 N的数列A1,A2,…AN如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K的倍数我们就称这个区间 [i,j]是 K倍区间。
你能求出数列中总共有多少个K倍区间吗?
### 数据范围
1≤N,K≤100000,
1≤Ai≤100000
//暴力写法o(n^2)会超时。
优化:在这里需要知道b[r] % k 和 b[l-1] % k 的余数如果相等,那么b[r] - b[l-1]的差值必然是k的倍数
例:当k==5时 6%5=1;16%5=1 得(16-6)%5==0;
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
long long a[N],b[N];
long long cnt[N],an;
int main()
{
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++)cin >> a[i];
int sum;
for(int i=1;i<=n;i++)
{
b[i]=b[i-1]+a[i];//前缀和处理
sum=b[i]%k;
an+=cnt[sum];
cnt[sum]++;
}//11001
cout << an+cnt[0];//cnt[0]是单个区间就是k的倍数。
}