暴力做法&&优化做法(带注释)
n^2的暴力做法,超时
#include <iostream>
using namespace std;
const int N = 1e5;
int s[N], q[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++)
{
scanf("%d", &q[i]);
s[i] = s[i - 1] + q[i];
}
int count = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
{
int t = s[j] - s[i - 1];
int p = t / k;
if(p * k == t) count++;
}
cout << count << endl;
return 0;
}
优化做法
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long s[N], cnt[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) //求前n项和
{
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
long long res = 0; //存放余数相等的个数,即有几个k倍区间
cnt[0] = 1; //范围是0 ~ n - 1,所以余数是0的数有一个s[0]
//注意:余数是之前的个本次的一样,就算区间和是k的倍数,并不是余数是0才是k的倍数
for (int i = 1; i <= n; i ++ ) //列举r的范围,l最多到r-1,所以res放在前面
{
res += cnt[s[i] % k]; //存放在此次r之前余数和 s[i] % k 相等的个数
cnt[s[i] % k]++; //将余数是此次 s[i] % k 的个数加一
}
cout << res;
return 0;
}