charmmm

用户名：1420462013

访问量：3395

签　名：

少年心怀乌托邦，心仍向阳肆生长

等　　级
排　　名	720
经　　验	3742
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	Bilibili
专　　业

　　自我简介：

TA的其他文章

1094：字符串的输入输出处理（C代码）
浏览：434

迷宫问题（C代码）
浏览：314

递增三元组（C代码）
浏览：652

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

蓝桥杯2017年第八届真题-k倍区间

　　作者: charmmm　　　　发表时间：2023-02-14 22:15:15 浏览：156　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-k倍区间

## 枚举，前缀和，同余定理

**解题思路**：用前缀和预处理 + 枚举区间两端点的时间复杂度是O(n^2^)的，不够高效。我们可以用一些数论知识进一步优化。

[同余定理](https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360)的一个重要结论：**两个数字对k同余，那么这两个数做差后模k等于0**。

我们可以用一个Map集合用来统计取余k余数相同的前缀和个数，例如map[1] = 3表示存在三个前缀和取余k的余数为1，由同余定理，这三个前缀和任意两两组合相减得到的区间之和一定可以整除k。在下表中`preSum[1]`和`preSum[2]`组合、`preSum[1]`和`preSum[5]`组合以及`preSum[2]`和`preSum[5]`组合所构成的区间分别是`[2,2]`、`[2,5]`以及`[3,5]`，这三个区间和都是k的倍数，满足题意。我们利用组合数公式`C3 2`就可以快速求得有三种组合方案。**需要注意的是**，我们忽略了无需组合，本身就是K倍区间的一些区间，比如`[1,3]`和`[1,4]`，则我们需要在最后的结果加上`map[0]`即可。

| 设 n = 5，k = 2 |      |      |      |      |      |
| --------------- | ---- | ---- | ---- | ---- | ---- |
| nums            | 1    | 2    | 3    | 4    | 5    |
| preSum          | 1    | 3    | 6    | 10   | 15   |
| preSum[i]%k     | 1    | 1    | 0    | 0    | 1    |
| map             | 2    | 3    |      |      |      |

```
import java.util.*;

public class Main {
    static int N = 100010; // K和N的数据范围一样
    static int[] preSum = new int[N];
    static int[] map = new int[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long res = 0; // 10^5个元素最多有(10^5*10^5)/2个区间，因此res用long来存
        int n = in.nextInt(),k = in.nextInt(),x;
        for (int i = 1; i<=n; ++i) {
            x = in.nextInt();
            preSum[i] = (preSum[i-1] + x)%k;
            ++map[preSum[i]]; // 将所有前缀和取余k(映射到0~k-1中)
        }
        for (int i = 0; i<k; ++i) {
            int cnt = map[i];
            res += (long)cnt*(cnt-1)/2; // 组合数Ccnt 2 的计算过程中可能会爆int
        }
        System.out.println(res+map[0]); // 最后加上本身区间为K倍区间的情况
    }
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

charmmm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

去掉双斜杠注释（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯2017年第八届真题-k倍区间

评论区

精彩推荐

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-排序问题<2> （C++代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

买不到的数目（C++代码）

c primer plus 第十二章 12.1小节

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

本人酷爱递归实现很多问题，这里也是

简单的a+b （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

charmmm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

去掉双斜杠注释 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯2017年第八届真题-k倍区间

评论区

精彩推荐

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-排序问题<2> （C++代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

买不到的数目 （C++代码）

c primer plus 第十二章 12.1小节

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

本人酷爱递归实现很多问题，这里也是

简单的a+b （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

去掉双斜杠注释（C语言代码）

　　评论区

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

买不到的数目（C++代码）