题目如下
问题描述
给定一个长度为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; }
刚看懂时：这个方法还真不是人能看懂的；
又看了一会：这理念自叹不如；
开始写博客后：我怕我解释完大家还是没看懂，[手动笑哭]。
