题目描述

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式

输出一个整数，代表 K 倍区间的数目。

数据范围

1≤N,K≤100000,
1≤Ai≤100000

输入样例

5 2
1
2
3
4
5

输出样例

6

暴力枚举 $O(n^3)$

算法思路:最外层循环固定区间的右端点r，第二层循环移动区间的左端点l [1,r]的区间，
当r=l的时候，区间只有一个数。第三层循环就是遍历区间[l,r]求和，判断sum[l,r]%==k

for(int r=1;r<=n;r++){
    for(int l=1;l<=r;l++){
        ll sum=0;
        for(int i=l,i<=r;i++)
            sum+=a[i];
        if(sum%k==0) res++;
    }
}

前缀和优化：$O(n^2)$

优化思路：当知道一个区间的左右端点，求区间和的时候，可以使用一维前缀和，那么可以将最里面的一层循环优化成O(1)

for(int r=1;r<=n;r++){
    for(int l=1;l<=r;l++){
        ll sum=s[r]-s[l-1];优化
        if(sum%k==0) res++;
    }
}

同余优化:$O(n)$

优化思路 ：判断条件是(s[r]-s[l-1])%k==0,将式子变形s[r]%k==s[l-1]%k(分配律)，
所以判别式就变为了，如果一个区间是k倍区间，那么k倍区间左端点的前一个位置s[l-1],右端点s[r]，
对k取余具有相同的余数(同余)

ll res=0;
for(int i=0;i<=n;i++){//i直接从0开始
    res+=cnt[s[i]%k];
    cnt[s[i]%k]++;
}

C++ 代码

#include<cstdio>
using namespace std;
typedef long long ll;
const int N=100010;
ll s[N];
ll cnt[N];
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) {//前缀和数组预处理
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    ll res=0;//res为ll型数据的原因：若区间长度为1e5时，所有的区间长度为1和2的区间都为k倍区间时，res为int就会爆掉
    for(int i=0;i<=n;i++){//i从0开始时，s[0]是等于0的，直接就初始化了cnt[0]=1,不需要再额外写cnt[0]=1
        res+=cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    printf("%lld\n",res);
    return 0;
}