题目知识点：前缀和->s[i]=s[i-1]+a[i]

解题分析：

刚看到这道题很快想到了前缀和的方法，按照枚举右端点的思路，遍历左端点，如果前缀和的差为
m的倍数，就res++;这样的时间复杂度为O(n^2),由于n<=1e5;所以这样肯定会超时，但是我自己没有想出来优化的方法，看了Y总的视频，优化方法真的很精妙。

优化思路：

由上边的O(n^2)的方法，其实是求在[1,n]范围内(s[r]-s[l-1])%m==0，变形后[0,n-1]范围内
(s[r]-s[l])%m==0,即s[r]%m==s[l]%m,如果两者取余后的值相同，则这两个数就可以为一个区间，所以在[1,n]内，计算每一个s[i]%m的值并将该值存入cnt数组中。一定要注意，这里是两两配对，而不是单个，这个地方就是为什么要cnt[0]=1初始化的原因。

时间复杂度

两个代码的时间复杂度均为O(n)

代码1：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int s[N];
int a[N];
int cnt[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    cnt[0]=1;  //不可以缺少，当只有一个s[i]%k==0时，这个区间是[0,i]!!!!!
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=(s[i-1]+a[i])%m; //证明1
        cnt[s[i]]++;
    }
    ll res=0;
    for(int i=0;i<m;i++){
        res+=(ll)cnt[i]*(cnt[i]-1)/2;//这里一定要有(long long ) ，表达式解释1
         //因为cnt[i]*(cnt[i]-1)/2原类型为int,但是计算后的值可能大于int,所以要用ll存储
    }
    cout<<res<<endl;

    return 0;
}

证明1：

(a+b) % p = (a%p + b %p) %p
(a%p + b) % p = (a%p%p + b %p) %p = (a+b) %p,
同理可得：
(a+b+c) %p = ((a%p + b) %p + c) %p

解释1：

s[i]全部是前缀和%m后的结果，即取值范围为[0,k-1]，选择两个构成一个区间，就是表达式：
Cn2 = n * (n-1)/2 = 1 + 2 + 3+…………+(n-1)

代码2：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll s[N];   //一定要注意前缀和一定是long long 类型，容易误写为int类型
int a[N];
int cnt[N];
int main(){

    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    ll res=0;           
    cnt[0]=1;              //必不可少！！！！
    for(int i=1;i<=n;i++){
        res+=cnt[s[i]%m]; //解释2
        cnt[s[i]%m]++;    //这两句的顺序不可以调换，否则结果错误
    }
    printf("%lld",res);
    return 0;

}

解释2：

为什么每多一个s[i]%k就需要res+=cnt[s[i]%m],就是这个s[i]与前边的%m值相同的s[j]进行配对，共有cnt[s[i]%m]种选择