k倍区间

问题描述

　　给定一个长度为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

#include<stdio.h>
#define N 100000 
int main()
{
    int a,b,shu[N],sum[N],cnt[N],k;
    scanf("%d %d",&a,&k);
    for(b=1;b<=a;b++)
    scanf("%d",&shu[b]);
    sum[0]=0;
    cnt[0]=1;
    for(b=1;b<=a;b++)
    {
        sum[b]=(sum[b-1]+shu[b])%k;//前缀和 
        cnt[sum[b]]++;
    }
     long long ans=0;
    for(b=0;b<k;b++) 
    {
      ans+=(long long)(cnt[b])*(cnt[b]-1)/2;
      }
       printf("%lld",ans);
       return 0;
}

注释：这道题是历届真题，还是一道压轴题，用枚举的方法是可一些出来的，但是他的测试数据非常大，运行超时，所以说简单的枚举是不行的，需要优化，然而简单的应用前缀和这个思想是不行，时间复杂度还是平方阶，这时候需要数学方法来解决，不愧是压轴题；