charmmm

用户名：1420462013

访问量：3852

签　名：

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

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

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-k倍区间
浏览：174

你可能喜欢

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

　　作者: charmmm　　　　发表时间：2023-02-14 22:15:15 浏览：174　|　评论：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.1 （C语言代码）

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

Lucky Word （C++代码）

不容易系列2 （C语言代码）

【蟠桃记】（C语言代码）

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

评论区

精彩推荐

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

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

九宫重排（C++代码）

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

母牛的故事（C语言代码）

人见人爱A+B （C语言代码）

求圆的面积（C语言代码）

妹子杀手的故事（C语言代码）

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

WU-拆分位数（C++代码）

charmmm

TA的其他文章

你可能喜欢

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

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

Lucky Word （C++代码）

不容易系列2 （C语言代码）

【蟠桃记】 （C语言代码）

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

评论区

精彩推荐

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

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

九宫重排 （C++代码）

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

母牛的故事 （C语言代码）

人见人爱A+B （C语言代码）

求圆的面积 （C语言代码）

妹子杀手的故事 （C语言代码）

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

WU-拆分位数 （C++代码）

【蟠桃记】（C语言代码）

　　评论区

九宫重排（C++代码）

母牛的故事（C语言代码）

求圆的面积（C语言代码）

妹子杀手的故事（C语言代码）

WU-拆分位数（C++代码）