题目描述
k倍区间(C语言小白版)
样例
//acwing K倍区间(前缀和)
//给定一个长度为N的数列,A1,A2,...AN
//如果其中一段连续的子序列Ai,Ai+1,...Aj之和是K的倍数
//我们就称这个区间是K倍区间
//目标:求出数列中总共有多少个K倍区间
#include <stdio.h>
#define N 100010
typedef long long LL;
int a[N],s[N];
int i;
int n,k;
LL res=0;
int cnt[N];//通过cnt[]数组,来记录余数是i的数有多少个
int main(){
printf("输入整数n表示数列的长度,整数k表示子序列之和需要是谁的倍数\n");
scanf("%d%d",&n,&k);
printf("输入数列的每一个数\n");
s[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];//转变为前缀和数组
}
//最初是在[1,r]找k倍区间[l,r]满足(s[r]-s[l-1])%k==0
//现在是在[0,r-1]找 (s[r]-s[l])%k==0,也就是s[l]%k==s[r]%k
//比如13%7和20%7余数相等,(20-13)%7=0
//也就是有多少个s[l]和s[r]余数相同就配成一对
cnt[0]=1;//cnt[0]=1是因为我们在找余数相同配对
//而余数等于0本身就满足条件不需要配对,所以当余数为0时直接加1就行
for(i=1;i<=n;i++){
res+=cnt[s[i]%k];//a[i] 0 1 2 3 4 5
cnt[s[i]%k]++; //s[i] 0 1 3 6 10 15
//s[i]%k 0 1 1 0 0 1
// res 0 +1 +1 +2 +2
//cnt++的原因是13%7=20%7=27%7=6
//那么20可以跟13配对,27可以跟13配对也可以跟20配对
}
printf("%d",res);
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla