暴力算法
#include<iostream>
using namespace std;
const int N = 100010;
int s[N],a[N];
int n,k;
int count=0;
int main()
{
cin>>n>>k;
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=a[i]+s[i-1];
}
for(int i=1;i<=n;i++)
{
// for(int j=1;j<=i; j++)
// {
// if((s[i] - s[j-1])% k ==0) count++;
// }
for(int j=0;j<i; j++)
{
if((s[i] - s[j])% k ==0) count++;
}
}
cout<<count;
return 0;
}
O(n)解法
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
LL s[N];
int cnt[N];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++)
scanf("%d", s + i), s[i] += s[i - 1]; //求前缀和
LL ans = 0;
cnt[0] = 1; //初始化 why 数本身能被k整除的个数
for(int i = 1; i <= n; i ++)
{
cout<<s[i]%k<<" ";
ans += cnt[s[i] % k];
cnt[s[i] % k] ++; // 前缀和取余k的余数的数量
}
cout<<endl;
cout << ans << endl;
}