题目描述
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗?
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数,代表 K 倍区间的数目。
数据范围
1≤N,K≤100000,
1≤Ai≤100000
样例
输入样例:
5 2
1
2
3
4
5
输出样例:
6
算法1(普通版)
(暴力枚举) $O(n^3)$
重点是要确定左右两个端点就行了
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
typedef long long ll;
int num[N];
ll ans;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
for (int i=1;i<=n;i++)
{
for (int j=i;j<=n;j++)
{
ll sum = 0;
for (int q=i;q<=j;q++) sum+=num[q];
if (sum%k==0) ++ans;
}
}
printf("%lld",ans);
return 0;
}
但是可以过30%左右的数据
算法2(升级版)
(暴力枚举+前缀和) $O(n^2)$
去掉一层循环:将for (int q=i;q<=j;q++) sum+=num[q];
化简,改写为前缀和形式
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
typedef long long ll;
ll S[N];
ll ans;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&S[i]);
S[i]+=S[i+1];
}
for (int i=1;i<=n;i++)
{
for (int j=i;j<=n;j++)
{
ll sum = S[j]-S[i-1];
if (sum%k==0) ++ans;
}
}
printf("%lld",ans);
return 0;
}
但是可以过60%左右的数据
算法3(最终版)
(数学知识+前缀和) $O(n)$
再去掉一层循环,将
for (int j=i;j<=n;j++)
{
ll sum = S[j]-S[i-1];
if (sum%k==0) ++ans;
}
利用数学知识改写,用到等式变形思想:
((S[j]-S[i-1])%k)==0 ----> (S[j]%k)==(S[i-1]%k)
进行枚举,不要忘了只有本身的情况!
C++ 代码
//没思路就先写暴力思路,再逐步优化(有没有做过类似的题目,一段一段看、想方法)
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
typedef long long ll;
ll S[N],cnt[N]; //如果数据取范围临界,可能会爆int
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%lld",&S[i]);
S[i] = S[i-1]+S[i]; //预处理前缀和
}
ll res = 0; //res也可能爆int
cnt[0] = 1; //只有自身一个数的情况
for (int i=1;i<=n;i++)
{
res+=cnt[S[i]%k];
cnt[S[i]%k]++; //叠加的思想,余数相同的两个数可以组成一对
}
printf("%lld",res);
return 0;
}