挑战赛#30 T4 题解

我说白了：前缀和+同余。

前缀和不讲。

首先是暴搜方法。
枚举每一个 $l,r\ (1\le l\le r\le n)$，判断是否能被 $M$ 整除。
代码（40pts）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,ans;
int a[N],s[N];
signed main(){
	cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=m;
        s[i]=s[i-1]+a[i];
    }
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            ans+=(s[j]-s[i-1])%m==0;
        }
    }
    cout<<ans;
	return 0;
}

进阶方法：同余。
前置知识：若 $a\equiv b \pmod m$，则 $m\mid(a-b)$。
这样，如果一个数（$a_r$）的前缀和与前面一个数（$a_l$）的前缀和同余，说明 $a_{l+1}+\cdots+a_r$ 能被 $M$ 整除。
即用一个数组统计每个数除以 $M$ 的余数，计算时前面有几个和这个数同余的答案就加多少。
当然如果这个数的前缀和能被 $M$ 整除，也要计算。所以数组中余数为 $0$ 的初始值要设置为 $1$。
代码（100pts）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,a,ans;
int r[N],s;//r[i] 表示除以 M 余数为 i 的数的数量，s 表示前缀和
signed main(){
	cin>>n>>m;
    r[0]=1;
    for (int i=1;i<=n;i++){
        cin>>a;
        a%=m;
        s+=a;
        ans+=r[(s%m+m)%m];//注意这个地方 s mod m 可能是负数
        r[(s%m+m)%m]++;
    }
    cout<<ans;
	return 0;
}