本文共 1861 字，大约阅读时间需要 6 分钟。

问题描述

给定一个长度为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

提示

资源约定：

峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：

main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

思路

比较容易想到的常规做法，是利用前缀和数组来保存整个数列的前缀和

然后再利用2层循环把所有的区间组合方案枚举出，对其中满足区间和为k的倍数的区间进行统计 最后输出结果即可 但是这里的数列最多达到了100000，在2层循环下，总的枚举次数就达到了O(1010)级，超时无疑 通常这种由数据范围带来的限制，往往需要通过数论的相关知识来进行优化 我们假设有一个序列为：5 2 4 7 3 1 6（且k=3），则其前缀和数组的增量对k取余的结果如下所示： a[ i ]表示该序列中的第 i 个数，S[ i ]表示该序列的前缀和增量对 k 取余的值（初始化S[0]=0） 不难看出，S[i]的取值在[0,k-1]之间，现在的问题是：这个值到底有什么用呢？ 答案：S[i]出现的次数说明了截至当前i，前面的k倍区间的数量 比如在i=2时，当前S[i]=1，这是数字1的第一次出现，任何数字的第一次出现都不能说明前面的k倍区间数量。但是当之后再次出现了数字1时（比如上表中i=6处），则表明现在的这个位置与前面出现数字1的位置之间构成了一个k倍区间（不包括前一个位置的那个值）。比如区间[3,6]（sum[3,6]=4+7+3+1=15，15%3=0）是一个k倍区间 继续看，在i=7时，S[i]=1又一次出现了，则表明在这个位置与其前面所有出现数字1的位置之间又能构成新的k倍区间（不包括前一个位置的那个值），比如区间[3,7]（um[3,7]=4+7+3+1+6=21，21%3=0）是一个k倍区间；同时，也有区间[7,7]（sum[7,7]=6，6%3=0）是一个k倍区间 …… 假设之后在某处i，又一次出现了数字1，那么该处又能与前面出现数字1的位置构成新的k倍区间。如果设在该处是数字1出现的第n次，那么此时能够构成的k倍区间就有n-1个，而总的k倍区间个数（包括前面所有的）则为：1+2+……+(n-1)

此时有同学就会提问了：如果是数字0第一次出现（假设为位置i），那么此时的区间[1,i]不也是一个k倍区间么？

这个提问是正确的，比如对于上面的序列，按照之前的思路，我们的流程如下： 当i=4时数字0第1次出现，但是不能说明前面的k倍区间的数量；接着当i=5时数字0第2次出现，则表明此时区间[5,5]（um[5,5]=3，3%3=0）是一个k倍区间 …… 就这样直到最后 而实际上，我们一开始就忽略了区间[1,4]（sum[1,4]=5+2+4+7=18，18%3=0）也是一个k倍区间，这样的忽略导致之后每出现一次数字0，就忽略一次。比如当第2次出现数字0时，我们又忽略了区间[1,5]（sum[1,5]=5+2+4+7+3=21，21%3=0）也是一个k倍区间…… 那么解决这个问题的办法也很简单，就是最后再单独加上一次所有的数字0出现的次数就行了 （思路参考于：https://blog.csdn.net/the_ZED/article/details/105046236）

代码：

#include
   
    #include
    
     int a[100010]={
   0};int b[100010]={
   0};int main(){
   	int N,K;	int t,i;	scanf("%d%d",&N,&K);	long long sum=0;		for(i=0;i
    
   

转载地址：https://blog.csdn.net/qq_45281807/article/details/108996318 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！