蓝桥杯练习题八 - k倍区间（c++）

题目如下

问题描述

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？

输入格式

第一行包含两个整数N和K。(1 <= N, K <= 100000)

以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出格式

输出一个整数，代表K倍区间的数目。

样例输入

5 2
1
2
3
4
5

样例输出

6

以下程序实现了该功能，请你补全空白处代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n, k, ans = 0, son[100000], sum[100000], b[100000] = {0};
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> son[i];
        if (i != 0)
            __________________;
        else
            sum[i] = son[i] % k;
        b[sum[i]]++;
        ans += b[sum[i]] - 1;
        if (sum[i] == 0)
            ans++;
    }
    cout << ans;
    return 0;
}

 预防针

兄弟们，不得不说，这道题是真难啊，看了一共5个小时左右，才把上面这种代码的思路看懂，外加另一种简单但却耗时的思路，网上也查了很多种解析，实在不敢恭维，很多人可能自己都没搞明白思路。除此之外，还有另一种解法，其实和本题给出的部分代码思路是一样的，不再单独列出，所以这里给出两种方法来解题。

代码解析一：以时间换空间（比较耗时的解法）

 代码如下：

#include <iostream>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int numMax,kVal,cnt,sumBuff;
    int numArray[100] = {0};
    
    cnt = 0;
    
    cin >> numMax >> kVal;
    for(int i = 0;i < numMax;i++) 
        cin >> numArray[i]; 
    
    for(int i = 0;i < numMax - 1;i++)
    {
        
        sumBuff = 0;
        for(int j = i;j < numMax;j++)
        {
            sumBuff += numArray[j];
            if(sumBuff % kVal == 0) cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}
 

1.将数字提前存入数组

    for(int i = 0;i < numMax;i++) 
        cin >> numArray[i]; 
    

2.循环累加

    for(int i = 0;i < numMax - 1;i++)
    {
        
        sumBuff = 0;
        for(int j = i;j < numMax;j++)
        {
            sumBuff += numArray[j];
            if(sumBuff % kVal == 0) cnt++;
        }
    }

i=0时，j所在的for循环：

j=0

第0次循环，sumBuff=numArray[0]，整除取余为0，cnt++；

第1次循环，sumBuff=numArray[0]+numArray[1],整除取余为0，cnt++；

.......

第numMax-1次循环，sumBuff=numArray[0]+......+numArray[numMax-1],整除取余后为0，cnt++。

i=1时，j所在的for循环：

j=1

第1次循环，sumBuff=numArray[1]，整除取余为0，cnt++；

.......

第numMax-1次循环，sumBuff=numArray[1]+......+numArray[numMax-1],整除取余后为0，cnt++。

......

i=numMax-2

j=numMax-2

第numMax-2次循环，sumBuff=numArray[numMax-2]，整除取余为0，cnt++；

第numMax-1次循环，sumBuff=numArray[numMax-2]+numArray[numMax-1],整除取余后为0，cnt++。

---

这种方式完全把numArray中任意块计算进去，不存在任何的遗漏，也是比较传统思维的一种解决方式，但是由于一个个的进行尝试，导致时间上会存在比较大的消耗，在实际应用中，可能会存在数量巨大的情况，所以这种方式并不被推崇。

代码解析二：以空间换时间（效率高）

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n, k, ans = 0, son[100000], sum[100000], b[100000] = {0};
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> son[i];
        if (i != 0)
            sum[i] = (sum[i - 1] + son[i]) % k;
        else
            sum[i] = son[i] % k;
        b[sum[i]]++;
        ans += b[sum[i]] - 1;
        if (sum[i] == 0)
            ans++;
    }
    cout << ans;
    return 0;
}

刚看懂时：这个方法还真不是人能看懂的；

又看了一会：这理念自叹不如；

开始写博客后：我怕我解释完大家还是没看懂，[手动笑哭]。

1.实时读取数据

        cin >> son[i];

2.获取sum[i]

        if (i != 0)
            sum[i] = (sum[i - 1] + son[i]) % k;
        else
            sum[i] = son[i] % k;

sum[i]我们都能理解，就是累加和嘛，可这里偏偏要%k是什么鬼意思？这里要当心了，一步看不懂，后面的全都看不懂了，我们把sum当做一个存储累加和余数的数组，我再强调一遍，“累加和余数”！！！！

所以:

当i == 0时，sum[i] = son[i] % k，即sum[0] = son[0] % k;

当i == 1时，sum[i] = (sum[i - 1] + son[i])% k，即sum[1] = (sum[0] + son[1]) % k;

 记住我说的，sum是余数和，后面你就忘掉那个“和”字，只记住“余数”，然后来展开下上面的公式：

sum[1] = (sum[0] + son[1]) % k;
sum[1] = sum[0] % k + son[1] % k;
sum[1] = sum[0] + son[1] % k; 
//sum[0]已经是余数了，所以%k没有意义，是本身

第一种解法，sumArray存储的是每一项从0开始的当前项的累加和；

这里sum存储的就是sumArray存储的是每一项从0开始的当前项余数的累加和；

3.先说sum[i] == 0的情况

        if (sum[i] == 0)
            ans++;

这个很明显，只要整数取余为0，那必然是符合k区间条件的，这里ans++应该不难理解，因为sum中存储的全是余数，必然不会全是0，有人会有疑惑，假如有多个不为0的余数存在，那么sum[i] == 0这个条件还能成立吗?答案是肯定的，这就是为什么余数也要进行相加的原因：

sum[i] = (sum[i - 1] + son[i]) % k;

余数（被忽略的部分必然被整除了）+余数（被忽略的部分必然被整除了）能被整除就是0，不能被整除就是另一个余数，也有可能和当前余数相等，相等怎么办？看下面：

4.区间计算的重头戏

b[sum[i]]++;
ans += b[sum[i]] - 1;

能不能看得懂就全看这里了！！！

b是什么？

b是用来存储相等的余数出现的次数的！！！

如果余数相等，则对应的i，j相减就把余数减去了，剩下的必定可以整除，这就是一个新的区间！！！

我们从0开始模拟下b：

假设余数为3:

余数3出现1次时：

b[3]++ = 1，说明余数为3的累加和出现1次，这时候没有成对出现，无法用j-i判断是否存在k倍区间；

余数3出现2次时：

b[3]++ = 2，说明余数为3的累加和出现2次，这时候存在1个k倍区间，为什么是1个呢？假设这2个累加和下表分别是i，j，那么有，j-i这个一个区间；

余数3出现3次时：

b[3]++ = 3，说明余数为3的累加和出现3次，这时候存在2个k倍区间，为什么是2个呢？假设这3个累加和下表分别是i，j，k，那么有，k-i，k-j，有人说，不是还有个j-i吗？没错，但是j-i已经在余数出现第2次的时候存在了，不能计算在内；

余数3出现4次时：

b[3]++ = 4，说明余数为3的累加和出现4次，这时候存在3个k倍区间，为什么是3个呢？假设这4个累加和下表分别是i，j，k，l那么有，l-i，l-j，l-k有人说，不是还有个j-i和k-i，k-j吗？没错！你抬头看看余数出现第2，3次的里面有没有没列出来的这三个？所以不能计算在内；

所以，你发现规律了吗？像不像选择排序法里面那样？用最后一个和前面的所有项比较，这还真是选择排序法里德运用。

ans += b[sum[i]] - 1;

这时候，你已经明白了b[sum[i]] 的含义，你可能还需要再消化下......

已经看懂的同学我们继续下一个问题，为什么要减1？

一个余数的时候，区间不成立；

两个相等余数的时候，两两比较，只能有1个；

三个相等余数的时候，最后一位和前两个比较，只有2个，

......

n个相等余数的时候，最后一位和前n-1个比较，只有n-1个.

因为始终有一个要作为参照系，所以只能存在n-1个，上面的举例已经清楚说明了原因。

---

总结

到这里，今天的学习就要结束了，说实话，这个题真TM难，就这，还被列入了简单之类，😂但是你要是听懂了，你会发现其实也不难，就是一个理念问题，可问题是，这样的理念不是一般人想的出来的。

另外，博主在查找的时候看到有些人的解析里面用到了c(m,n)，这是什么呢？

从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。所以它叫排列组合，记得大学里面高数里讲概率的时候有讲过，相信很多人都忘了。根据这种理论，会有一种新的写法，但思路和第二种是一样的，我们是直接通过从n个余数中找出有几种组合的方式，c(m,n)是根据数学的思维通过公式计算sumArray中存在余数的组合方式：

1  2  3  4  5

son[]

1  2  3  4  5

1  0  1  0  1 每一项整除取余

这里是2个

sum[]

1  3  6  10  15

1  1  0  0   1  累加和整除取余

 这里1是c(3,2)=3;

这里0是c(2,2)=1;

2 + 3 + 1 = 6

感兴趣的可以去了解下这种方式，不再赘述，有问题欢迎评论区留言讨论。