思路

先用前缀和数组存储1～i（i=1,2,···,n）的连续序列和，传统思路为遍历所有可能的区间左右端点然后判断是否为K倍区间，时间复杂度$O(n^2)=10^{10}$会TLE，故采用空间换时间的优化做法

$\Rightarrow优化:$(S[r]-S[l])%K==0等价于S[r]与S[l]模K同余，故在计算S[i]的同时可以使用一个数组存储S[i]模K的余数

从余数相同的数中任取两个作为S数组的索引然后作差，得到的结果就是满足条件的一个K倍区间

注意

1.mod[0]初值要赋为1，因为S[0]=0，S[0]%K=0，任何一个前缀和减去S[0]得到的序列为该前缀和对应的区间，它也可能是K倍区间

2.避免大整数相乘爆int范围，最好扩大到long long

3.为了避免负数模上K得到负索引范围的情况，采用mod[(num[i] % K + K) % K]++代替mod[num[i] % K]++

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, K;
ll num[(int)1e5 + 10];
ll mod[(int)1e5 + 10] = {1};
ll ans;

ll C(ll x)
{
    return x * (x - 1) / 2;
}

int main()
{
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++)
    {
        scanf("%lld", &num[i]), num[i] += num[i - 1];
        mod[(num[i] % K + K) % K]++;
    }
    for (int i = 0; i < K; i++)
        ans += C(mod[i]);
    printf("%lld", ans);
    return 0;
}