一定不要忘记long long,一开始直接前缀和+暴力过一半O(n^2)超时,然后优化成O(n)和O(k)的方式
思路:循环遍历前缀和数组s,更新res的值,res累加上前缀和对k取模的次数,然后更新cnt数组中对应前缀和对k取模后的次数
方法一:O(n)
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int N=1e5+10;
int a[N],cnt[N];
long long s[N],res;
int main()
{
int n=read();int k=read();
for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
cnt[0]=1;//表示前缀和为0时出现一次
for(int i=1;i<=n;i++) res+=cnt[s[i]%k],cnt[s[i]%k]++;
cout<<res<<'\n';
return 0;
}
方法二:用哈希表,时间复杂度O(k),少开了一个cnt数组
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;}
const int N=1e5+10;
int a[N];
long long res;
int main()
{
int n=read(),k=read();
unordered_map<int,int> cnt;
int sum=0;
cnt[0]=1;//同上
for(int i=1;i<=n;i++){
a[i]=read();
sum=(sum+a[i])%k;//防止爆long long
if(sum<0) sum+=k;
res+=cnt[sum];
cnt[sum]++;
}
cout<<res<<'\n';
return 0;
}