自动搬运

查看原文

来自洛谷，原作者为

	UNDERTALE_RS To wish upon a S.A.T.E.L.L.I.T.E.

搬运于2025-08-24 21:17:08，当前版本为作者最后更新于2024-12-28 20:37:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题目传送门

前置知识

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

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

题目分析

看到题目，我们思考一下，题目简化后就是问 $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;
}

总结

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

感谢您的阅读！