算法1
(暴力枚举) $O(n^2)$
暴力时间复杂度O(n^2),只能过一半样例
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int a[N];
int n;
int k;
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
a[i]+=a[i-1];
for(int len=0;len<n;len++){//区间长度
for(int i=1;i<=n-len;i++){//不同位置
if((a[i+len]-a[i-1])%k==0) ans++;//如果模为0则为一种情况
}
}
cout<<ans;
return 0;
}
算法2
(数学优化) $O(n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int n;
int k;
int a[N];
int cnt[N];
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
cnt[0]=1;//余数为0说明本身是可以被整除的
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];//前缀和
ans+=cnt[a[i]%k];//再出现模相同就加上
cnt[a[i]%k]++;//存入不同模
}
cout<<ans;
return 0;
}