K倍区间
有N个数的数列A1,A2,...,An，定义S(i, j) = Ai+Ai+1+……+Aj(i<=j)。如果S(i, j)能被正整数k整除，那么称S(i, j)为K倍区间。
测试数据共两行。第一行为两个正整数N和k，第二行为N个不同的正整数。
输入样例1：
5 2
1 2 3 4 5
输入样例2：
5 3
1 2 3 4 5
输出样例1：
6
输出样例2：
7
样例1解释：这6个区间分别为[2,2], [4,4], [1,3], [3, 5], [1, 4], [2, 5]
题解：
以sum(i)表示A1+A2+……+Ai，那么S(i, j) = sum(j) - sum(i-1)。K倍区间满足S(i, j) % K == 0，则[sum(j) - sum(i-1)] % K == 0，变换为sum(j) % K == sum(i-1) % K。可以边读入Ai边计算sum(i)，同时做模K运算。然后，对于sum(R)，假设有x个sum(L)(L<R)的值与sum(R)相同，那么就有x个k倍区间，累加到答案中。
参考代码：
#include<stdio.h> #include<string.h> #define maxn 100001 int cnt[maxn], a[maxn]; __int64 sum; int main() { int n, k; scanf("%d %d", &n, &k); int i; for(i = 1; i <= n; i++) { scanf("%d", &a[i]); } memset(cnt, 0, sizeof(cnt)); a[0] = 0; for(i = 1; i <= n; i++) { a[i] = (a[i] + a[i-1]) % k; } sum = 0; cnt[0] = 1; for(i = 1; i <= n; i++) { sum += (__int64)cnt[a[i]]; cnt[a[i]]++; } printf("%I64d\n", sum); return 0; }