问题描述

　　给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。 　　你能求出数列中总共有多少个K倍区间吗？

输入格式

　　第一行包含两个整数N和K。(1 <= N, K <= 100000) 　　以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出格式

　　输出一个整数，代表K倍区间的数目。

样例输入

5 2 1 2 3 4 5

样例输出

6

数据规模和约定

　　峰值内存消耗（含虚拟机） < 256M 　　CPU消耗 < 2000ms

思路:(sum[r]-sum[l-1])%k == 0.即：sum[r]%k==sum[l-1]%k 

当l==r时,也可能是K倍区间,最后再补上

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define loop(i,L,R) for(int i=(L);i<=(R);i++) const int maxn=1e5+5; int a[maxn],sum[maxn],bk[maxn]; int main() { int n,k; scanf("%d%d",&n,&k); rep(i,n) scanf("%d",&a[i]); a[0]%=k; sum[0]=a[0]; loop(i,1,n-1) { sum[i]=(sum[i-1]+a[i])%k; } ll ans=0; rep(i,n) { ans+=(1LL*bk[sum[i]]++); } printf("%lld\n",ans+bk[0]); }