【蓝桥杯】省赛真题—K倍区间（前缀和，数学，思维）

• 一学就会的小技巧（一）：前缀和
• 一学就会的小技巧（二）：差分
• 一学就会的小技巧（三）：快速幂
• 一学就会的小技巧（四）：龟速乘
• 一学就会的小技巧（五）：矩阵快速幂
• 一学就会的小技巧（六）：矩阵快速幂的应用
• 数论基础—素数筛、最大公约数、最小公倍数

🌻🌻在之前的几篇文章中介绍了前缀和，以及同余定理这几个知识点，正好就在这道题派上用场了，一起来看看吧~

☕K倍区间：

题目链接：https://www.lanqiao.cn/problems/97/learning/

⭐题目要我们找区间，所以无脑使用前缀和数组sum[]预处理输入。

⭐如果枚举所有区间和，即便使用了前缀和，时间复杂度可以到 O ( N 2 ) O(N^2) O(N2)，依然会有几个样例超时。

⭐回忆一下同余定理，题目让我们寻找k倍区间，即$(sum[r]-sum[l-1])\mathrm{m}\mathrm{o}\mathrm{d}k=0$，移项可得$sum[r]\mathrm{m}\mathrm{o}\mathrm{d}k=sum[l-1]\mathrm{m}\mathrm{o}\mathrm{d}k$，换句话说就是让我们找有多少个前缀和$sum[i]$模$k$后相等，比如模$k$后相等的$sum[i]$有n个，那么从中任取两个代入前面的公式都可以找出一个k倍区间。

⭐同时对于任意$sum[i]\mathrm{m}\mathrm{o}\mathrm{d}k$，其结果只可能是0 ~ k-1，因此可以用一个哈希表记录$sum[i]\mathrm{m}\mathrm{o}\mathrm{d}k$相等的个数，由组合数 C n 2 C_{n}^{2} Cn2​ (0 <= n <= k-1)可以求出模相等的前缀和可以得到几个k倍区间，这样，我们遍历哈希表，将所有可以由结果相同的前缀和求模得到的k倍区间累加起来就是最终答案。

🍦AC代码（Java）:

import java.util.Scanner;public class Main {    // 后面用不到原数列，所以只存储前缀和    public static int[] sum = new int[100005];    // 用来统计相同余数的的个数    public static long[] remainder = new long[100005]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); long ans = 0; // 前0项和是0，注意余数为0开始就出现一次 remainder[0] = 1; int n = sc.nextInt(); int k = sc.nextInt(); for (int i = 1; i <= n; i++) {     int num = sc.nextInt();     sum[i] = (sum[i - 1] + num) % k;     remainder[sum[i]]++; } sc.close(); for (int i = 0; i < k; i++)     ans += (remainder[i] * (remainder[i] - 1)) >> 1; System.out.println(ans);    }}

🍌🍌🍌
一道蓝桥杯省赛真题，用到了前面几篇文章讲到的前缀和与同余定理，正好可以巩固加强一下之前学过的知识~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~

驱动天空下载