算法1
(暴力枚举) $O(n^2)$
暴力枚举每一个区间,最后TLE了,评测28分/100分
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++) s[i] = s[i-1] + a[i];
int res = 0;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j++)
{
if((s[j] - s[i-1]) % k ==0) res ++;
}
}
cout << res;
return 0;
}
算法2
(前缀和) $O(n)$
若两个前缀和模k的值相等,则其相减后就是k的倍数。
参考文献
y总蓝桥杯辅导课
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N], s[N];
LL cnt[N]; //若s[i]%k=x,cnt[x]记录的就是有多少个这样的前缀和是模k等于x的
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i ++) s[i] = s[i-1] + a[i]; //前缀和
LL res = 0;
cnt[0] = 1; //该前缀和本身就是k的倍数
for(int i = 1; i <= n; i ++)
{
res = res + cnt[s[i] % k];
cnt[s[i] % k] ++;
}
cout << res;
return 0;
}