小L的区间求和

题目描述

在给定的一个整数序列中，小L希望找到一个连续的区间，这个区间的和能够被k整除，请你帮小L算一下满足条件的最长的区间长度是多少。

输入

第一行输入两个整数n、k。（1 <= n <= 105,1<=k<100）
接下来一行输入n个整数，表示序列中的数。

输出

输出一个整数，满足条件区间的最长长度，如果不存在，输出0

样例输入 Copy

5 7
1 2 4 1 1

样例输出 Copy

3

题解：开一个数组要来记录前n项对K取余的余数，，再开一个数组，用来记录余数第一次出现的位置
要点1 当一个 余数数组 的的前几项和为0的时候，从开头到此处的和是K的倍数
要点2 当一个余数重复出现的时候，说明从该余数第一次出现的位置（不包括第一次）到该次出现的位置的和味K的倍数（仔细想想还是很有道理的）
例如 2%10=2  （2+10）%10 =2 所以当两个余数相同时，期间一定加上了k的倍数。关键就是前面的前n项和的余数数组有点难理解。} 

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+7;
int arr[N];
int s[N];
int pre[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        s[i]=(s[i-1]+arr[i])%m;//保存前缀和的数组
        pre[s[i]]=-1;//每个余数的位置的初始化为-1 
    }
    pre[0]=0;//0比较特殊，因为出现了0，说明从开头到现在都可以被K整除
    int ans=0; 
    for(int i=1;i<=n;i++){
        if(pre[s[i]]==-1){
            pre[s[i]]=i;//为-1的话说明该余数第一次出现，保存一下位置 
        }
        else {
            ans=max(ans,i-pre[s[i]]);
        }
    } 
    cout<<ans<<endl;
    return 0;
}