今天leetcode题实在太简单，所以就做一道蓝桥题吧

先看数据范围-1e5

先杜绝一切暴力想法。开始分解问题。很明显可以转化为前缀和的差值为k的倍数。

得到pre[i]-pre[j-1]%k==0寻找所有的i和j，O（n2）很明显会超时。

转化一下问题，我们知道一个数%k最多有0~k-1一共k种可能。

得到pre[i]%k==pre[j-1]%k，也就是说这两者的前缀和%k得到的余数相同，那我们很容易想到用一个哈希去存然后计数（记得开ll！）

是非成败转头空，不开long long见祖宗！

余数为零的第一次只要自己一个数就可以作为答案区间，剩下都需要至少两个，所以>=2才第一次++

除余数为0以外都需要两个数组合，所以从第二个开始计数，并且每次新找到一个余数为k的数都可以和原来找到的cnt[k]个元素组合，所以ans加上上一次cnt[k]里面的个数就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
using i64=long long;
const int N =100010;
i64 pre[N],cnt[N];
i64 res;
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n,k;
  cnt[0] = 1;//余数为零的第一次只要自己一个数就可以作为答案区间，剩下都需要至少两个，所以>=2才第一次++
  cin >> n >> k;

  for(int i = 1; i <= n; i ++ )
  {
      cin >> pre[i];
      pre[i] += pre[i - 1];//优化空间

      res += cnt[pre[i] % k];//除余数为0以外都需要两个数组合，所以从第二个开始计数
      cnt[pre[i] % k]++ ;
  }
  cout << res;
  return 0;
}