算法1

借鉴TonyJam的做法

分析

求区间和，可以通过前缀和来求出。sum[r]−sum[l−1]sum[r]−sum[l−1]就是区间[l,r]的和。如果区间[l,r]的和是k的倍数则有(sum[r]−sum[l−1])，即sum[r]。因此，我们可以得到一个结论，对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间。

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p + p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
(a^b) % p = ((a % p)^b) % p （4）

有了这个结论之后，我们就可以使用两层for循环来计数k倍区间的个数，但是由于数据比较大，我们不能这样做。那么我们能不能在计算前缀和的过程中同时来统计k倍区间的个数呢？当然可以。我们可以用一个数组cnt，规定cnt[i]表示当前位置之前，前缀和取模后等于i的个数，以后每出现一次前缀和（取模后）和它相等，那么k倍区间就加上cnt[sum[i]]，然后cnt[sum[i]]++。这样似乎不容易理解，我们用样例举个例子。

对于数列 1 2 3 4 5，k = 2

对前1个数的和模k后为1，在此之前有0个前缀和取模后为1，总个数+0

对前2个数的和模k后为1，在此之前有1个前缀和取模后为1，总个数+1

对前3个数的和模k后为0，在此之前有0个前缀和取模后为0, 总个数+0

对前4个数的和模k后为0，在此之前有1个前缀和取模后为0，总个数+1

对前5个数的和模k后为1，在此之前有2个前缀和取模后为1，总个数+2

但是我们还忽略了一点，就是我们这样做我们少计算了区间[0,i][0,i]构成的k倍区间，其个数为cnt[0]。

关于cnt[0]

就是之前每次累加答案的时候都没有考虑0-i这个区间也满足题意的情况（部分和左区间要-1，但是那样就会越界）。
数组左边多加一格写零就可以不用这样

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;

int n, k;

int sum[100005], cnt[100005];

long long ans = 0;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        sum[i] += (sum[i - 1] + x) % k;//   求前缀和 
        ans += cnt[sum[i]];//    加上在此之前与它同余的前缀和（模k后） 
        cnt[sum[i]]++;//    对前缀和模k后的余数统计出现次数 
    }
    printf("%lld", ans + cnt[0]);
    return 0;
}