Edward 得到了一个长度为 N 的整数序列，他想找出这里面有多少个“幸运的” 连续子序列。一个连续子序列被称为“幸运的”，当且仅当该子序列内的整数之 和恰好是 K 的整数倍数。他请求你写一个程序来计算他喜欢的连续子序列个数。
Edward 得到了一个长度为 N 的整数序列，他想找出这里面有多少个“幸运的” 连续子序列。一个连续子序列被称为“幸运的”，当且仅当该子序列内的整数之 和恰好是 K 的整数倍数。他请求你写一个程序来计算他喜欢的连续子序列个数。
输入第一行是一个整数 T，表示有 T 组数据。 每组数据第一行是两个整数 N (1 <= N <= 106), K (1 <= K <= 109)。 接下来的一行包含 N 个整数 Ai (|Ai| <= 109)。
对于每组测试数据，输出一行仅包含一个整数，表示 Edward 喜欢的连续子序 列数量。
2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2
4
9
链接：http://www.homeforaoge.com/problem.php?id=1210
思路：利用同余模定理，另外负数取余时，余数d=(a%K+k)%k;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define N 1000005
#define ll long long
const int inf=0x7fffffff;
int s[N];
int main()
{
int T,i,n,k,a;
ll ans,cnt;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
scanf("%d",&s[0]);
s[0]%=k;
if(s[0]<0)
s[0]=(s[0]+k)%k;
for(i=1; i<n; i++)
{
scanf("%d",&a);
s[i]=s[i-1]+a;
s[i]%=k;
if(s[i]<0)
s[i]=(s[i]+k)%k;
}
sort(s,s+n);
ans=0;
s[n]=inf;
for(i=1,cnt=1; i<=n; i++)
{
if(s[i]==s[i-1])
cnt++;
else
{
if(s[i-1]!=0)
cnt--;
ans+=(cnt+1)*cnt/2;
cnt=1;
}
}
printf("%lld\n",ans);
}
return 0;
}
原文：http://www.cnblogs.com/walker11/p/4357533.html