这里是题目链接 k倍区间
题目大意 简单来说，给你一个数组和一个数k，让你满足数组中连续区间和为k的倍数的区间有几个
思路 看到题目的连续区间的时候，就知道这题使用前缀和来写的，然后我喜闻乐见的TLE了 ，咳咳，看了题目100000组数据，那n2数据妥妥的过不了了，只能是看看怎么画了，于是想到一个定理，(A-B)mod k= A mod k - B mod k这样就有思路了
为了说明方便，我们设这个数组有{1，2，3，4，5}，k为2
首先,对于数组num， 我们算出它的各个前缀和的余数，然后依此遍历，设一个计数的数组cnt[i]表示余数为 i 的个数，这样，遍历过程中，有两种情况
1.当前元素余数为1，则此时，由上面的（A-B）mod k =A mod k -B mod k可知，增加的k倍区间个数为cnt[1]的值.简单来说，cnt[1]为之前找到余数为1的前缀和的个数，如果cnt[1]>0，那么前面至少有一个余数为1的前缀和，和一个余数为1的当前的前缀和序列，则这两个序列之间的余数差为0，则意味着两个余数为1的前缀和，他们之间的区间就是k倍区间，所以当增加的k倍区间个数有cnt[1]个
2.当前元素余数为0的情况差不多，增加的k倍区间个数为cnt[0]个
注意到了最后，我们还要格外给答案加上cnt[0]的值，因为余数为0的前缀和本身也是一个k倍区间呀！
那么剩下的代码问题就很简单了
#include <iostream> using namespace std; const int MAXN = 100000+5; int num[MAXN],cnt[MAXN]; int main() { int n,k; cin>>n>>k; for(int i=0; i<n; i++) { cin>>num[i]; } num[0]%=k; for(int i=1;i<n;i++){ num[i]=(num[i]+num[i-1])%k; } // for(int i=0;i<n;i++){ // printf("num[%d]=%d\n",i,num[i]) // } long long ans=0; for(int i=0;i<n;i++){ ans+=(cnt[num[i]]); cnt[num[i]]++; // printf("cnt[%d]=%d ans=%d\n",num[i],cnt[num[i]],ans); } cout<<ans+cnt[0]<<endl; return 0; }