【蓝桥杯学习记录】K倍区间
一、题目
给定一个长度为N的数列，A1, A2, ...... AN ，如果其中一段连续的子序列Ai,Ai+1, ...... Aj( i≤j ) 之和是K的倍数，我们就称这个区间 [i, j][i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗？
第一行包含两个整数 N 和 K
以下 N 行每行包含一个整数 Ai
输出一个整数，代表 K 倍区间的数目。
二、数学知识
(a-b)%K==0等价于a&K==b%K
三、解题思路
本题很容易想到暴力的做法，就是用一个三层循环，但是这样会超时。于是可以用前缀和，即sum[i]=A[1]+A[2]+·······A[i]。这样每一个区间[i,j]的和就可以表示为sum[j]-sum[i]。由上面数学知识讲到的等价式可知，我们想得到区间和对K取余==0，就是任意两个前缀和对K取余得到的余数相等所以我们可以计算一下所有前缀和对K取余的余数的个数，并且用组合数公式来得到一共有几个组合，即有几个K倍区间。
四、完整代码
五、出现的问题
本来用暴力方法就已经超时了，我在改成前缀和时又把求余数新加了一个循环，导致又超时了，挺笨的。还有就是测试数据有100000个，而我开始把数组S设成了[100000]，但是我又弃用了S[0]导致数组越界了，另外答案很大，需要用long long类型
六、参考资料
https://www.jianshu.com/p/3ed28f2bbcad
https://www.bbsmax.com/A/6pdD24EKJw/
