题解：B4105 [CSP-X2024 山东] 消灭怪兽

· · 题解

B4105 [CSP-X2024 山东] 消灭怪兽 题解

题目传送门

前置知识

如果两个正整数 a，b 除以同一个正整数 k 的余数相等，则这两个数同余。记作：

a \equiv b \pmod k

同时两数之差能被 k 整除。即：

k \mid (a - b)

题目分析

看到题目，我们思考一下，题目简化后就是问 n 个数中有多少个区间和是 k 的倍数。

题目中说到：

1 \le n \le 10^6

所以即使是前缀和也需要用优化的方法。

前缀和

提到区间和离不开的就是前缀和。那么我们就对输入的数进行前缀和的处理。

计算个数

我们知道区间和的计算方法，就是在前缀和数组中的右端点位置的数减去左端点位置的前一个数。

根据前置知识，要求以 n 个数中的某个数为结尾的区间和为 k 的倍数的区间个数，
就是在前缀和数组里找其之前与它的前缀和关于 k 同余的数的个数。

这样我们就可以用一个计数数组来存储每一个前缀和模 k 的情况。
代码如下：

long long a[1000005],qzh[1000005],cnt[1000005];
for(int i = 1;i <= n;i++){
    cin >> a[i];
    qzh[i] = qzh[i-1] + a[i]; //前缀和数组
    ans += cnt[qzh[i] % k]; //以现在为结尾的区间个数
    cnt[qzh[i] % k]++; //将模k的情况记录，不可调换顺序！
}

答案输出

输出答案前我们仔细想就会发现，最终的 ans 没有记录到单个数的情况，所以最后输出还要补上。
最终代码如下：

#include <iostream>
using namespace std;
long long n,a[1000005],qzh[1000005],cnt[1000005],ans,k;

int main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        qzh[i] = qzh[i-1] + a[i];
        ans += cnt[qzh[i] % k];
        cnt[qzh[i] % k]++;
    }
    cout << ans+cnt[0]; //cnt[0]为单个数的情况
    return 0;
}

总结

是一道基础的题，考察数学能力，需要对余数有相关认识，适合初学者练习。

感谢您的阅读！