AcWing 1230. K倍区间 C++满分题解

原题链接https://www.acwing.com/problem/content/1232/

题目分析

求区间和，我们可以通过前缀和来求出。

我们规定sum[i]表示第1个元素到第i个元素的和。那么sum[r] - sum[l-1]就是区间[l,r]的和。

一维前缀和

for (int i = 1; i <= n; i ++ ){
    scanf("%lld", &sum[i]);
    sum[i] += sum[i - 1];
}

线性同余定理：sum[r] % k 和 sum[l-1] % k 如果相等，那么sum[r] - sum[l-1]的差值必然是k的倍数

代码细节

求和值和结果均可能达到1e10数量级，因此用Long Long定义sum[N],cnt[N]和res;

当输入时就建立好前缀和数组

for循环遍历前缀和数组，首先把第i个当作sum[right]，前面有几个同余数的前缀和，res就加几。

然后将第i个当作sum[left](增加了sum[left]的数量)

C++代码

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

typedef long long LL;
const int N = 1e5 + 5;
int n, k;
LL sum[N], cnt[N];//cnt统计每个余数对应的前缀和个数 

int main(){
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ){
        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];
    }
    
    LL res = 0; 
    cnt[0] = 1;//假设第0个数字余数是0； 
    for (int i = 1; i <= n; i ++ ){
        res += cnt[sum[i] % k];//检查第i个数字前缀和前面有几个前缀和与它同余 
        cnt[sum[i] % k] ++ ;
    }
    printf("%lld\n", res);
    return 0;
}