蓝桥杯K倍区间（前缀和与差分，取模化简）

输入
5 2
1 2 3 4 5
输出
6

思路：首先由连续子串和可以想用前缀和，由于加减法总和取模和分别取模结果不受影响，所以我们前缀和之后直接取模方便观察性质，本题前缀和：1，3，6，10，15取模之后：1，1，0，0，1，用差分就可以求出某段区间的和，如果该段区间和取模2为0，那么答案+1，但是如果直接for循环差分o(N**2)会超时，不妨找取模后的数组中相等的数，因为这样两数相减=0（取模后为0，那么没取模的时候一定是2的倍数）即可，只要o(n).

细节：

（1）由于差分找到的区间的左开右闭的，当有独立的前缀和=0，那么从一开始到它这段连续序列是可以的，未来避免单独讨论，在读入a[N],s[N]时我们从1 开始，最后找相同数字时我们从 0 开始。

（2）ans+=c[sum[i]];
        c[sum[i]]++;这个顺序不能反，只有碰到>=2个相等才能有效

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,k,ans=0;
int a[N],sum[N],c[N];
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];//sum[i-1]=0sum[i]%=k;}for(int i=0;i<=n;i++ ){ans+=c[sum[i]];c[sum[i]]++;}cout<<ans<<endl;return 0;}