问题： 有多少连续区间元素之和 %k == 0
    暴力思想：l, r两个指针遍历所有区间的可能性，然后用前缀和进行O(1)的判断 时间复杂度O(n^2)

    如何优化 公式：(s[r] - s[l - 1]) % k; 
    引入同余定理：给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除
    即（a-b）/m得到一个整数，那么就称整数a与b对模m同余 

    用大白话说：两个数相减模m=0,则a % m = b % mod

    因此公式：(s[r] - s[l - 1]) % k; 可简化为一维，s[r] % k = s[l - 1] % k
    即用cnt数组记录%k的结果的个数
    ll res += cnt[s[i] % k]

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], cnt[N];
ll s[N];
ll res;
int n, k;
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    cnt[0] = 1;//就样例而言 a[2] = 2  2 % 2 = 0，是符合条件的，因此初始化赋值cnt[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        res += cnt[s[i] % k] ++;
    }
    cout << res;
    return 0;
}