蓝桥 k倍区间 (前缀和)

题目描述
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
输出一个整数，代表K倍区间的数目。
样例输入
5 2
1
2
3
4
5
样例输出
6

用sum[i]表示[1,i]的区间和，那么对于一个区间[l,r], 可以用sum[r]-sum[l-1]来表示。
要求区间和整除k的，需要(sum[r]-sum[l-1])%k==0 ---》sum[r]%k=sum[l-1]%k.
也就是当处理到i时，要看前面有多少个%k相同的，也就是到当前位置为结尾的区间和为k整数倍的个数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

int a[100005];
int cnt[100005];
int sum[100005];
int main(){
   
    int n, k;
    cin>>n>>k;
    ll res=0; 
    for (int i=1; i<=n; i++){
   
        scanf("%d", &a[i]);
        sum[i]=(sum[i-1]+a[i])%k;    //[1,i]和对k求余结果 
        res+=cnt[sum[i]];//前面有几个相同的余数结果，到这里就有几个k倍 
        cnt[sum[i]]++;    //[1,i]和%k的个数 
    }
    cout<<res+cnt[0];    //单独的一个k整数倍也可以 
    return 0;
}

        

          
        
        
        

          

          AI 代码解读